[Acwing] 346.走廊泼水节 Kruskal+并查集维护集合大小

前言

传送门 :

前言

我们知道 K r u s k a l Kruskal Kruskal 每次是对两个集合进行操作,也就是一个集合中的点不可能与另

一个集合相连。也就是为了构成完全图我们必须知道这两个集合中的大小,然后我

们一一连边根据乘法原理也就是 s i z e [ a ] ∗ s i z e [ b ] − 1 size[a]*size[b]-1 size[a]∗size[b]−1

但是需要连一条大小多少的边呢?因为 k r u s k a l kruskal kruskal是排序过的,所以为了保证最小生树

的唯一性和不变性,我们需要令加的边为当前的 w + 1 w+1 w+1即可

CODE

int n,m,t;
int p[N],size1[N];

struct node{
	int a,b;double w;
	bool operatora>>b>>c;
		e[i] = {a,b,c};
	}
	
	sort(e+1,e+n);
	ll ans = 0;
	for(int i=1;i