AcWing 346. 走廊泼水节
原题链接
中等
作者:
LiuHH
,
2020-08-25 21:49:46
,
所有人可见
,
阅读 528
/*
思路:
用了kruskal算法的思想,将图看做是一块一块的图,而连接这些一块一块之间的图的边(长度记作 len)就是唯一的生成树上
的边,将不同块之间用边连接成完全图,这条边的长度应该为 len + 1;
执行步骤:
1.按边的权排序
2.选一条最短得边,将该边连接的两个块(如果这个块是不同的)连接成完全图
3.继续执行第2步,直到遍历所有点,算法结束
为什么算法结束,整个图就变为了完全图? 因为kruskal算法的正确性保证了算法结束后所有的点都被加入了同一个块
为什么连接两个块的长度为 len + 1 ? 因为, 对于当前两个块来说它们之间连接的边的长度为len,如果选的边比len要小,那么将会
产生一条更小的边连接这两个块,将破坏唯一的最小生成树这个条件。
*/
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 6010;
struct Node{
int u,v,w;
bool operator < (const Node& t1) const{
return w < t1.w;
}
}e[N];
int n,m;
int col[N],nums[N];
int find(int a){
if(col[a] != a) col[a] = find(col[a]);
return col[a];
}
int kruskal(){
int res = 0;
sort(e,e + n - 1);
for(int i = 1; i <= m; i++) col[i] = i,nums[i] = 1;
for(int i = 0; i < n - 1; i++){
int f1 = find(e[i].u), f2 = find(e[i].v);
if(f1 != f2){
col[f2] = f1;
int d = e[i].w + 1;
res += (nums[f1] * nums[f2] - 1) * d;
nums[f1] += nums[f2],nums[f2] = 0;
}
}
return res;
}
int main(){
int t;
cin >> t;
while(t--){
cin >> n;
m = -1;
for(int i = 0; i < n - 1; i++) {
int u,v,w;
cin >> u >> v >> w;
m = max(max(u,v),m);
e[i] = {u,v,w};
}
printf("%d\n",kruskal());
}
return 0;
}