[USACO14JAN]Ski Course Rating G

• 2020 年 11 月 21 日
• 筆記
• 并查集

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

Slove

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

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

Code

#include<bits/stdc++.h>
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<xx2.c;
	else 
	{
		if(xx1.a!=xx2.a)return xx1.a<xx2.a;
		else return xx1.b<xx2.b;
	}
}
int m,n,t,bcj[1000000],tot=0,lll;
long long mm[1000][1000],num[1000000],siz[1000000],ans=0;
int find(int x)//并查集-找祖宗
{
	int zz;
	if(bcj[x]==x)zz=x;
	else zz=find(bcj[x]);
	bcj[x]=zz;
	return zz;
}
int main()
{
	scanf("%d%d%d",&m,&n,&t);
	for(int i=1;i<=m*n*3;i++)bcj[i]=i,siz[i]=1;//预处理
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)cin>>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]<t)ans+=s[i].c*num[fa];
			if(siz[fb]<t)ans+=s[i].c*num[fb];
		}
		num[fa]+=num[fb],siz[fa]+=siz[fb],bcj[fb]=fa;//合并信息
	}
	cout<<ans<<endl;

	return 0; 
}