给出一个完全图唯一最小生成树,求完全图所有边权的和
考场想到n^2log的计算,枚举两点再求出两点路上最长边再判断要不要+1.没想到就是个kruskal水题
const int N = 23007;
struct edge {
int x, y, z;
bool operator <(const edge&rhs) const {
return z < rhs.z;
}
} t[N];
int n, T;
int fa[N], siz[N];
inline int find(int x) {
while(x != fa[x]) x = fa[x] = fa[fa[x]];
return x;
}
int main() {
freopen("sheep.in","r",stdin);
freopen("sheep.out","w",stdout);
read(T);
while(T--) {
read(n);
rep(i, 1, n) {
fa[i] = i;
siz[i] = 1;
}
lxl ans(0);
rep(i, 2, n) {
read(t[i - 1].x);
read(t[i - 1].y);
read(t[i - 1].z);
ans += t[i - 1].z;
}
std::sort(t + 1, t + n);
rep(i, 1, n - 1) {
int x(find(t[i].x));
int y(find(t[i].y));
if(x == y) continue;
ans += 1ll * (t[i].z + 1) * (siz[x] * siz[y] - 1);
fa[x] = y;
siz[y] += siz[x];
}
out(ans, '\n');
}
return 0;
}