走廊泼水节——求维持最小生成树的完全图的最小边权和

题目

思考

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
const int M = N;
int p[N], sz[N];
struct edge{int a;int b;int c;bool operator < (const edge& v) const{return c < v.c;}
}e[M];
int find(int x)
{if(p[x] != x) p[x] = find(p[x]);return p[x];
}
int t, n;
int main()
{cin >> t;while(t--){cin >> n;for(int i = 1; i <= n; i++)p[i] = i, sz[i] = 1;for(int i = 1; i <= n-1; i++){int a, b, c;cin >> a >> b >> c;e[i] = {a, b, c};}sort(e+1,e+n);int res = 0;for(int i = 1; i <= n-1; i++){int a = e[i].a, b = e[i].b, c = e[i].c;a = find(a), b = find(b);//if(a == b) continue; 这里不用判断是否是同类边，因为题目给的就是树，刚好连通，不可能同类res += (c+1) * (sz[a] * sz[b] - 1);sz[b] += sz[a];p[a] = b;}cout << res << '\n';}
}