Author: lllyouo
Date: 20250225
tag: 最小生成树、并查集
link: https://www.acwing.com/problem/content/348/

问题描述

link

分析

考虑 Kruskal 算法的执行过程：当两个连通块合并时，存在一条边 $(x,y,z)$，点 $x$ 属于连通块 $A$ 点 $y$ 属于连通块 $B$。对于 $A,B$ 每个连通块中的点而言，为了让它们两两之间都有一条边，且加上边后不改变整棵树的最小生成树，那么加上的边的权值至少为 $z+1$，且需要加 $S_A\ast S_B-1$ 条边（其中 $S_A,S_B$ 表示连通块 $A,B$ 中点的数量），则增加的权值之和为 $(z+1)\ast (S_A\ast S_B-1)$。在算法执行过程中连通块合并时累加该值即可。

参考代码

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

const int N = 6010;
struct NODE {
    int u, v, w;
    
    bool operator < (const NODE& x) {
        return w < x.w;
    }
} e[N];
int t, n, p[N], siz[N];

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

int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        for (int i = 0; i < n - 1; i++) {
            cin >> e[i].u >> e[i].v >> e[i].w;
        }
        sort(e, e + n - 1);
        for (int i = 1; i <= n; i++) p[i] = i, siz[i] = 1;
        
        int ans = 0;
        for (int i = 0; i < n - 1; i++) {
            int fu = find(e[i].u);
            int fv = find(e[i].v);
            
            if (fu != fv) {
                ans += (e[i].w + 1) * (siz[fu] * siz[fv] - 1);
                p[fv] = fu;
                siz[fu] += siz[fv];
            }
        }
        cout << ans << endl;
    }
    
    return 0;
}