走廊泼水节题解

链接

题目描述：

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

补充知识

完全图

在图论的数学领域，完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。

思路：

根据Kruskal算法的原理，任何一棵最小生成树一定包含无向图中权值最小的边。所以要保证当前的树是补充完后的完全图的最小生成树，我们每次在两个并查集之间加的边都要比当前边要大1， 我们要增加的边数等于两个并查集的节点数的乘积-1，通过Kruskal算法遍历原图生成最小生成树时添加边即可ac

代码

s表示并查集中的节点数

f表示父亲节点

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,y,z;
}a[6011];
int f[6011],s[6011];
bool cmp(node a,node b){
    return a.z < b.z;
}
int F(int x){
    if(x == f[x]) return x;
    return f[x] = F(f[x]);
}
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        for(int i = 1; i < n; i++){
            cin >> a[i].x >> a[i].y >> a[i].z;
        }
        for(int i = 1; i <= n; i++){
            f[i] = i;
            s[i] = 1;
        }
        sort(a + 1, a + n, cmp);
        long long ans = 0;
        for(int i = 1; i < n; i++){
            int u = F(a[i].x);
            int v = F(a[i].y);
            int w = a[i].z;
            if(u!=v){
                f[u] = v;
                ans += (s[v] * s[u] - 1) * (w + 1);
                s[v] += s[u];
            }
        }
        cout << ans << endl;
    }
}
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