[USACO14JAN]Ski Course Rating G

题目链接：https://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;

}

巴特西

[USACO14JAN]Ski Course Rating G

Slove

Code

最新文章

热门文章