题解 P5429 【[USACO19OPEN]Fence Planning】

2019-05-29 20:14:17


拿并查集维护连通性就可以了。

复杂度 $O((n+m)\log n)$ 。

代码:

#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;
}