题解：P6171 [USACO16FEB] Fenced In G

Big_Dinosaur · 2024-10-23 19:33:44 · 题解

请先看看网格图。

下文 a_{n+1}=A,b_{m+1}=B,a_0=b_0=0。

思路转化

将矩阵中各个点联通，可以考虑转化为最小生成树。边权为拆除栅栏长度。

如果你画一下图，你可以发现此时该图为网格图，网格图第 i 行第 j 列的点与第 i+1 行第 j 列之间的边权为 b_{j+1}-b_j，第 i 行第 j 列的点与第 i 行第 j+1 列之间的边权为 a_{i+1}-a_i。

接下来，你可以发现：同一行边的边权相等，同一列的边权相等。

这可以转化为 P5687 网格图。

注意：a,b 不按升序给出，要先排序！

Code

#include<bits/stdc++.h>
#define int long long
#define ri register int
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
const int TXYAKIOI=1145141919810;
const int JYAAKIOI=0x3f3f3f3f3f3f3f3f;
using namespace std;
namespace IO{
    char ibuf[(1<<20)+1],*iS,*iT;
    #if ONLINE_JUDGE
        #define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
    #else
        #define gh() getchar()
    #endif
    inline int r(){
        int o=1,p=0;
        char q=gh();
        while(q<'0'||q>'9'){if(q=='-')o=-1;q=gh();}
        while(q>='0'&&q<='9'){p=(p<<1)+(p<<3)+(q^48);q=gh();}
        return o*p;
    }
    inline char gc(){char q=gh();while(q<=' ')q=gh();return q;}
    inline string gs(){string s="";char g=gh();while(g<=' ')g=gh();while(g>' '){s+=g;g=gh();}return s;}
    inline void Wi(int E){
        if(E==0)return;if(E<0){E=-E;putchar('-');}
        Wi(E/10);putchar((E%10)^48);
    }
    inline void wln(int J){if(J==0)putchar('0');else Wi(J);putchar('\n');}
    inline void w(int J){if(J==0)putchar('0');else Wi(J);}
    inline void ww(int J){if(J==0)putchar('0');else Wi(J);putchar(' ');}
}
using namespace IO;
namespace D1n0{
    int n,m,A[256666],B[256666],a[256666],b[256666],X,Y;
    inline void zyt(){
        X=r(),Y=r(),n=r(),m=r();
        for(ri i=1;i<=n;++i)A[i]=r();sort(A+1,A+1+n);
        for(ri i=1;i<=m;++i)B[i]=r();sort(B+1,B+1+m);
//转换
        for(ri i=1;i<=n;++i)a[i]=A[i]-A[i-1];a[n+1]=X-A[n];
        for(ri i=1;i<=m;++i)b[i]=B[i]-B[i-1];b[m+1]=Y-B[m];
        ++n,++m;
//网格图代码
        sort(a+1,a+1+n);
        sort(b+1,b+1+m);
        int t1=m-1,t2=n-1,S=a[1]*(m-1)+b[1]*(n-1);
        for(ri i=2,j=2;i<=n&&j<=m;){
            if(a[i]<b[j])S+=a[i]*t1,--t2,++i;
            else S+=b[j]*t2,--t1,++j;
        }
        wln(S);
    }
}
signed main(){
    D1n0::zyt();
}