[USACO14JAN]Ski Course Rating G

题目链接：https://www.luogu.com.cn/problem/P3101

Slove

这题我们可以尝试建立一个图。
以相邻的两个点建边，边的权值为两个点高度差的绝对值，然后把边按照边权值从小到大排序。

然后就可以愉快地使用并查集了：
一开始将每一个点划分到自己的集合。
每次枚举一条边，判断所枚举的边的两个点是否在同一个集合内，如果在就不管，不在就将这两个节点所处的集合进行合并。
每枚举一条边，如果发现合并后的集合点数已经不少于t个，且合并前有集合的点数小于t，如果以前这个集合里面包含终点，答案就直接加上当前边的权值就好了。
每次集合合并时需要合并的信息有集合大小和集合中是否含起点

Code

#include
using namespace std;
struct bian
{
    int a,b;
    long long c;
}s[1000000];
int cmp(bian xx1,bian xx2)
{
    if(xx1.c!=xx2.c)return xx1.c>mm[i][j];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            if(i!=1)s[++tot].a=(i-1)*n+j,s[tot].b=(i-2)*n+j,s[tot].c=abs(mm[i][j]-mm[i-1][j]);
            if(j!=1)s[++tot].a=(i-1)*n+j,s[tot].b=(i-1)*n+j-1,s[tot].c=abs(mm[i][j]-mm[i][j-1]);
        }
        //建边
    sort(s+1,s+tot+1,cmp);//排序
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&lll);
            if(lll==1)num[(i-1)*n+j]=1;//给起点打上标记(第i行第j列的点编号为((i-1)*n+j))
        }
    for(int i=1;i<=tot;i++)
    {
        int fa=find(s[i].a),fb=find(s[i].b);
        if(fa==fb)continue;//在同一个集合中
        if(siz[fa]+siz[fb]>=t)//判断集合是否满足条件
        {
            if(siz[fa]