走廊泼水节

原题链接

题目描述

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

求增加的边的权值总和最小是多少。

注意： 树中的所有边权均为整数，且新加的所有边权也必须为整数。

---

思路

初始时先将每一个点看成一个大小为 \(1\) 的连通块，这个连通块就可以看成一个完全图(因为只有一个点)

做 Kruskal 算法，在每循环到一条可以合并两个连通块的边 \(e\) 时，记 \(e\) 的边长为 \(w\),为了形成一个完全图，就要使得两个已经是完全图的连通块中的点有边，但是为了使最后的唯一最小生成树还是原来那棵而且，新增的边一定要大于 \(w\)：

1. 假设新边小于 \(w\)，因为新增边后会成环，当断开边 \(e\)，形成的树大小会变小，即不是原来那棵，所以不成立
2. 假设新边等于 \(w\)，同样的断开 \(e\)，会形成一个大小一样但结构不一样的树，不满足唯一，所以也不成立。

所以只要在每次新增 \(e\) 的时候，给两个连通块内的点增加 \(w+1\) 长的边即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 6010;

int n;
int siz[N], p[N];
struct Edge {
    int a, b, w;
    bool operator < (const Edge &W) const {
        return w < W.w;
    }
};

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void solve() {
    cin >> n;
    vector<Edge> E(n - 1);

    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        E[i] = {a, b, w};
    }

    // kruskal
    for (int i = 1; i <= n; i++) {
        p[i] = i;
        siz[i] = 1;
    }

    sort(E.begin(), E.end());

    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        int a = E[i].a, b = E[i].b, w = E[i].w;
        a = find(a);
        b = find(b);

        p[a] = b;
        res += (siz[b] * siz[a] - 1) * (w + 1);
        siz[b] += siz[a];
    }

    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}