P5036 随机生成树

题意概括

其实就是满足要求的连通块数量最大值。

思路

可以很快地想到 Kruskal 算法，但这题的难点不在这。

难点在于其要求的排序方式：

对连通块有贡献的优先。
满足条件一时，编号之和最小的优先。
同时满足条件二时，连接的两个点编号的之中较小的一个较小的边优先。

这里的排序条件

cmp

应该是：

CPP

bool cmp(edge a,edge b){
	if (a.w==b.w){
		if (a.u+a.v==b.u+b.v){
			return min(a.u,a.v)<min(b.u,b.v);
		}
		return a.u+a.v<b.u+b.v;
	}
	return a.w>b.w;
}

还有一个需要考虑的是如何判断贡献：

如果一条边的两端点的颜色

c[i]

和

c[i]

是相同的，显而易见的，连通块的数量会少，也就是其对生成连通块没有贡献。

代码

最后是代码，其他的注释都在里面了：

CPP

#include <bits/stdc++.h>
using namespace std;

const int N=500005;

int n,c[N],f[N],cnt;		//声明变量 

struct edge{
	int u,v,w;		//边要开多一点 
}e[10000005];

int find(int x){
	if (x==f[x]) return x;
	else return f[x]=find(f[x]);		//经典并查集 
}

bool cmp(edge a,edge b){		//排序规则 
	if (a.w==b.w){
		if (a.u+a.v==b.u+b.v){
			return min(a.u,a.v)<min(b.u,b.v);
		}
		return a.u+a.v<b.u+b.v;
	}
	return a.w>b.w;
}

void kruskal(){
	for (int i=1;i<=cnt;i++){
		int fa1=find(e[i].u);
		int fa2=find(e[i].v);
		if (fa1==fa2) continue;
		f[fa1]=fa2;
		cout << e[i].u << " " << e[i].v << endl;		//Kruskal 
	}
}

int main(){
	cin >> n;
	for (int i=1;i<=n;i++) cin >> c[i];		//读入 
	for (int i=1;i<=n;i++) f[i]=i;		//初始化 
	for (int i=1;i<=n;i++){
		for (int j=i*2;j<=n;j+=i){		//这里可以满足题里必须要连自身约数倍数 
			e[++cnt].u=i;
			e[cnt].v=j;
			if (c[i]==c[j]) e[cnt].w=-114514;
			else e[cnt].w=1919810;
		}		//只要能分辨就行，数字不重要 
	}
	sort(e+1,e+1+cnt,cmp);		//排序
	kruskal();
	return 0;
}

题解：P5036 随机生成树

文章操作

P5036 随机生成树

题意概括

思路

代码

相关推荐

评论

题解：P5036 随机生成树