题解 P5429 【[USACO19OPEN]Fence Planning】

拿并查集维护连通性就可以了。 复杂度 $O((n+m)\log n)$ 。 代码: ```cpp #include<cctype> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<iostream> #define Rep(i,a,b) for(register int i=(a);i<=(b);++i) #define Repe(i,a,b) for(register int i=(a);i>=(b);--i) #define rep(i,a,b) for(register int i=(a);i<(b);++i) #define pb push_back #define mp make_pair typedef unsigned long long uint64; typedef unsigned int uint32; typedef long long ll; using namespace std; namespace IO { const uint32 Buffsize=1<<15,Output=1<<23; static char Ch[Buffsize],*S=Ch,*T=Ch; inline char getc() { return((S==T)&&(T=(S=Ch)+fread(Ch,1,Buffsize,stdin),S==T)?0:*S++); } static char Out[Output],*nowps=Out; inline void flush(){fwrite(Out,1,nowps-Out,stdout);nowps=Out;} template<typename T>inline void read(T&x) { x=0;static char ch;T f=1; for(ch=getc();!isdigit(ch);ch=getc())if(ch=='-')f=-1; for(;isdigit(ch);ch=getc())x=x*10+(ch^48); x*=f; } template<typename T>inline void write(T x,char ch='\n') { if(!x)*nowps++='0'; if(x<0)*nowps++='-',x=-x; static uint32 sta[111],tp; for(tp=0;x;x/=10)sta[++tp]=x%10; for(;tp;*nowps++=sta[tp--]^48); *nowps++=ch; } } using IO::read; using IO::write; using IO::getc; using IO::flush; inline void Chkmin(int&u,int v){u>v?u=v:0;} inline void Chkmax(int&u,int v){u<v?u=v:0;} inline void file() { #ifndef ONLINE_JUDGE freopen("water.in","r",stdin); freopen("water.out","w",stdout); #endif } const int MAXN=1e5+7; static int n,m,mxx[MAXN],mxy[MAXN],mnx[MAXN],mny[MAXN]; static int fa[MAXN]; inline int fd(int u){return u==fa[u]?u:fa[u]=fd(fa[u]);} inline void merge(int u,int v){u=fd(u),v=fd(v);if(u^v)fa[u]=v;} inline void init() { read(n),read(m); Rep(i,1,n)read(mxx[i]),read(mxy[i]),mnx[i]=mxx[i],mny[i]=mxy[i]; Rep(i,1,n)fa[i]=i; static int u,v; Rep(i,1,m)read(u),read(v),merge(u,v); } inline void solve() { Rep(i,1,n) { int f=fd(i); Chkmax(mxx[f],mxx[i]),Chkmin(mnx[f],mnx[i]); Chkmax(mxy[f],mxy[i]),Chkmin(mny[f],mny[i]); } static int ans=1e9; Rep(i,1,n)if(fa[i]==i)Chkmin(ans,mxx[i]+mxy[i]-mnx[i]-mny[i]); cout<<ans*2<<endl; } int main() { file(); init(); solve(); return 0; } ```