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

前言

传送门 :

前言

我们知道 $Kruskal$ 每次是对两个集合进行操作,也就是一个集合中的点不可能与另

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

们一一连边根据乘法原理也就是$size[a]\ast size[b]-1$

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

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

CODE

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

struct node{
	int a,b;double w;
	bool operator<(const node &W)const{
		return w<W.w;
	}
}e[N*N];
void init()
{
	for(int i=1;i<=N;i++)
	{
		p[i] = i;
		size1[i]=1;
	}
}
int find(int x)
{
	if(x!=p[x])return p[x]  =find(p[x]);
	return p[x];
}


void solve()
{
	cin>>n;
	init();
	
	for(int i=1;i<n;i++)
	{
		int a,b;double c;
		cin>>a>>b>>c;
		e[i] = {a,b,c};
	}
	
	sort(e+1,e+n);
	ll ans = 0;
	for(int i=1;i<n;i++)
	{
		int a  = e[i].a,b = e[i].b,w=e[i].w;
		a = find(a),b=find(b);
		if(a ==  b)continue;
		
		ans+=1ll*(size1[a]*size1[b]-1)*(w+1);
		p[a] =b;
		size1[b] +=size1[a];
	}
	cout<<ans<<endl;
	
	
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53