走廊泼水节【最小生成树变种】

https://www.acwing.com/problem/content/description/348/

题意：给定一棵N个节点的树，要求增加若干条边，
把这棵树扩充为完全图，并满足图的唯一最小生成树仍然是这棵树。

求增加的边的权值总和最小是多少。
1
2
3
4

思路 克鲁斯卡尔变种
        使用并查集
		把边排序，如果俩端不在同一集合，连边，权重为w
		要成为完全图，其他边权重为w+1，边数为：俩个集合点数乘积
		另外开s数组记录
1
2
3
4
5

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=6666;
struct node{
    int a,b,c;
    bool operator<(const node& t){
        return c<t.c;
    }
};
node edge[6666];

int f[N],s[N];
int get(int x){
    return x==f[x]?x:f[x]=get(f[x]);
}

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++){
            f[i]=i,s[i]=1;
        }
        for(int i=0;i<n-1;i++){
            cin>>edge[i].a>>edge[i].b>>edge[i].c;

        }
        long long int res=0;
        sort(edge,edge+n-1);
        for(int i=0;i<n-1;i++){
            int x=edge[i].a,y=edge[i].b,w=edge[i].c;
            int fx=get(x);
            int fy=get(y);
            if(fx==fy) continue;
            res+=1ll*(s[fy]*s[fx]-1)*(w+1);
            f[fx]=fy;
            s[fy]+=s[fx];
        }
        cout<<res<<endl;
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46