【最小生成树】CH_6201 走廊泼水节

本文主要是介绍【最小生成树】CH_6201 走廊泼水节，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意

给出一颗$N$个点的树，要求加入若干边，使得这棵树变成完全图，且图中的最小生成树还是这颗树。求边权总和最小是多少。

思路

类似$kruskal$算法的过程，对于一条边，如果它们的两个点属于两个不同的集合，那么这些集合间都要连边，为保证最小生成树还是数据给出的树，我们就让它们都连上$v+1$。

代码

#include<cstdio>
#include<algorithm>struct node{int x, y, v;
}e[6001];
int T, N;
long long ans;
int s[6001], fa[6001];int cmp(node x, node y) {return x.v < y.v;
}int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);
}int main() {scanf("%d", &T);for (; T; T--) {ans = 0;scanf("%d", &N);for (int i = 1; i <= N; i++) {fa[i] = i;s[i] = 1;}for (int i = 1; i < N; i++)scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].v);std::sort(e + 1, e + N, cmp);for (int i = 1; i < N; i++) {int a = find(e[i].x);int b = find(e[i].y);if (a != b) {fa[b] = a;ans += (s[a] * s[b] - 1) * (e[i].v + 1);s[a] += s[b];//统计集合中点的个数}}printf("%lld\n", ans);}
}

这篇关于【最小生成树】CH_6201 走廊泼水节的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---