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

题目

思考

代码

#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';
    }
}