Kruskal的经典扩展
题意：将一棵树扩展成一个完全图，保证该树是图的唯一最小生成树
关键思想：将一棵树看成是点集由集合合并组成的，每一次集合合并，都建构两个集合之间除树边以外的图边，由Kru算法的原来可知，最短的图边长度是w+1；
Code：
#include<bits/stdc++.h>
using namespace std;
const int N = 6010;
int n, t;
int p[N];
struct Edge {
int a, b, c;
bool operator<(const Edge& other) { return c < other.c; }
}e[N];
int siz[N];
int find(int x) {
if (p[x] != x)p[x] = find(p[x]);
return p[x];
}
int main() {
cin >> t;
while (t--) {
int res = 0;
cin >> n;
for (int i = 1; i <= n; i++)p[i] = i, siz[i] = 1;
for (int i = 0; i < n - 1; i++) {
int x, y, z;
cin >> x >> y >> z;
e[i] = { x,y,z };
}
sort(e, e + n - 1);
for (int i = 0; i < n - 1; i++) {
int a = find(e[i].a), b = find(e[i].b), w = e[i].c;
if (a != b) {
res += (siz[a] * siz[b] - 1)*(w + 1);
siz[b] += siz[a];
p[a] = b;
}
}
cout << res << endl;
}
}