AcWing 346 走廊泼水节

题目传送门

一、做法

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

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

• 假设新边小于\(w\)，因为新增边后会成环，当断开边\(e\)，形成的树大小会变小，即不是原来那棵，所以不成立

• 假设新边等于\(w\)，同样的断开\(e\)，会形成一个大小一样但结构不一样的树，不满足唯一，所以也不成立。

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

证明：得出来的完全图中的最小生成树是原来那棵。(反证法)

假设最后生成的完全同中的最小生成树不是原来那棵，在原树中，从小到大遍历\(n-1\)条边，找出第一条不在新最小生成树中的边，在新树中将它连上，会形成一个环，由之前加边时的操作可以知道，在这个环中一定存在一条长度大于它的边，断开这更大条，会形成一个更小的树，那就不是最小生成树，所以假设不成立。

二、实现代码

#include 
using namespace std;

const int N = 6010;
// Kruskal的结构体
struct Edge {
    int a, b, w;
    bool operator<(const Edge &ed) const {
        return w < ed.w;
    }
} edge[N];

int n;
int cnt[N]; //配合并查集使用的，记录家族人员数量
int p[N];   //并查集
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) p[i] = i, cnt[i] = 1;
        int m = n - 1;
        //录入n-1条边
        for (int i = 0; i < m; i++) {
            int a, b, c;
            cin >> a >> b >> c;
            edge[i] = {a, b, c};
        }
        //排序
        sort(edge, edge + m);

        int res = 0;
        for (int i = 0; i < m; i++) {
            auto e = edge[i];
            int a = find(e.a), b = find(e.b), w = e.w;
            if (a != b) {
                // a集合数量，b集合数量，相乘，但需要减去已经建立的最小生成权这条边
                // w是最小的，其它的可以建立最小也得大于w,即w+1
                res += (cnt[a] * cnt[b] - 1) * (w + 1);
                p[a] = b;         //合并到同一集合
                cnt[b] += cnt[a]; // b家族人数增加cnt[a]个
            }
        }
        //输出
        cout << res << endl;
    }
    return 0;
}