AcWing 走廊泼水节题解

这道题大致题意就是让一棵树任意两点有连边（也就是完全图），但是补完后最小生成树是一开始的那棵树，问最小加的边权之和是多少。

了解题意后，我们可以想到用Kruskal（废话），当每两个集合合并的时候，除了本身的那条边，一共还会加上\(siz_i * siz_j - 1\)条边，那么每条边的大小也就是边\(i,j\)的长度\(+1\)了，具体的可以看下代码。

代码：

#include <bits/stdc++.h>

using namespace std;

struct node{

	int l , r , w;

};

node e[6010];

int ans = 0 , n;

int vis[6010][6010] , fa[6010] , siz[6010];

bool cmp(node &x , node &y){

	return x.w < y.w;

}

int find(int x){

	if(x == fa[x]) return x;

	return fa[x] = find(fa[x]);

}

int main(){

	int T;

	cin >> T;

	while(T--){

		cin >> n;

		for(int i = 1; i <= n - 1; i++) cin >> e[i].l >> e[i].r >> e[i].w;

		for(int i = 1; i <= n; i++) fa[i] = i , siz[i] = 1;	//多维护一个siz

		sort(e + 1 , e + n , cmp);

		ans = 0;

		for(int i = 1; i <= n - 1; i++){

			int x = find(e[i].l) , y = find(e[i].r);

			fa[x] = y;

			ans += (siz[y] * siz[x] - 1) * (e[i].w + 1);

			siz[y] += siz[x];

		}

		cout << ans << endl;

	}

	return 0;

}

巴特西

AcWing 走廊泼水节题解

最新文章

热门文章

巴特西

AcWing 走廊泼水节 题解

最新文章

热门文章

AcWing 走廊泼水节题解