题解 P3141 【[USACO16FEB]围栏Fenced In_Platinum】
本题就是最小生成树模型，但只会最小生成树是不够的~~~
楼下说的其实不对，因为我就是用Kruskal算法的~
但如果你不会Kruskal也可以往下看，因为并没有涉及太多的MST知识。
推导需要一步步来哦
初始
就用最基本的最小生成树算法
把所有的区域都看成是点，每拆掉一个围栏就相当于加上一条边，这样其实就是MST了。
但是！！！不要高兴太早，关注一下本题的数量级，（1<=n,m<=25,000），然而其中的区域至少有n*m个，再加上Kruskal的排序，呵呵......
观察
注意一下，由于每一条围栏都是平行于所对应的边框的，所以，同一列的水平围栏长度相同，同一行的竖直围栏也长度相等。
这样就可以把水平围栏和竖直围栏分开算了，直接删去整行或整列。
是不是很简单？？？
但是，在删的过程中，由于到后面，并不是一整行或一整列上所有的围栏都要删去，有的删去甚至会出现环路，所以......
用x数组记录水平围栏的长度，用y数组记录竖直围栏的长度。
x1......xn+1，y1......ym+1
再用i,j两个指针记录当前扫到第几行或列。
当i,j都大于1的时候：
由于当x[i]<y[j]的时候，肯定要删第i列的水平栅栏，该列的栅栏个数为m(行数)-j(已经删了多少行)+1，对列有影响的是行（列与列不相交）
//不太理解可以自己画一个图，突然想吐槽题面的图了，居然都碎了~~~
当x[i]>y[j]的时候，肯定要删第j行的竖直栅栏，该行的栅栏个数为n(列数)-i(已经删了多少列)+1，对行有影响的是列（行与行不相交）
剩下的就看代码吧......
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=25003;
long long ans,x[N],y[N],n,m,A,B,a[N],b[N];
int i,j;
int FAST_READ()//快速读入
{
int tot=0;char c;
for(c=getchar();c==' '||c=='\n';c=getchar());
while(c>='0'&&c<='9')
tot=tot*10+c-'0',c=getchar();
return tot;
}
int main()
{
A=FAST_READ();B=FAST_READ();n=FAST_READ();m=FAST_READ();
for(i=1;i<=n;i++)
a[i]=FAST_READ();
for(i=1;i<=m;i++)
b[i]=FAST_READ();
sort(a+1,a+n+1);sort(b+1,b+m+1);//注意，位置不是按升序给的
for(i=1,x[n+1]=A-a[n];i<=n;i++)
x[i]=a[i]-a[i-1];//记录间隔两行之间的水平围栏的长度，在0和n的位置人为加上围栏，方便计算
for(i=1,y[m+1]=B-b[m];i<=m;i++)
y[i]=b[i]-b[i-1];//同上
n++;m++;
sort(x+1,x+n+1);sort(y+1,y+m+1);//因为是最小，所以要排个序，有点贪心的感觉
for(i=2,j=2,ans=x[1]*(m-1)+y[1]*(n-1);i<=n&&j<=m;)//i,j都为1时，预先处理
if(x[i]<y[j])
ans+=x[i++]*(m-j+1);
else
ans+=y[j++]*(n-i+1);
printf("%lld\n",ans);
return 0;
}