首页 程序设计 图与树 最小生成树

# 背景

给定一个 nn 个点 mm 条边的无向图，图中可能存在重边和自环，边权可能为负数
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible

最小生成树
给定一张边带权的无向图 G=(V,E)G=(V,E)，其中 VV 表示图中点的集合，EE 表示图中边的集合，n=∣V∣n=|V|，m=∣E∣m=|E|
由 VV 中的全部 nn 个顶点和 EE 中的 n−1n-1 条边构成的无向连通子图被称为 GG 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 GG 的最小生成树

# 数据范围

  • 1≤n≤1051 \le n \le 10^5
  • 1≤m≤2×1051 \le m \le 2 \times 10^5

# 思路

KruskalKruskal 算法用于解决稠密图的最小生成树

  • 对输入的边按边权值大小升序排列（这也是 KruskalKruskal 算法时间复杂度的主要来源）
  • 遍历所有边
    • 如果当前边不在 “集合” 里，则加入到集合中
    • 若在，则继续遍历下一条
  • 最后判断总结点数是否等于 nn 即可
    C++
    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
    struct Point {
        int a, b, c;
    } p[M];

    int n, m, f[N];

    bool cmp(Point x, Point y) {
        return x.c < y.c;
    }

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

    void solve () {
        cin >> n >> m;
        for (int i = 1, a, b, c; i <= m; i++)
            cin >> a >> b >> c, p[i] = {a, b, c};
        sort(p + 1, p + m + 1, cmp);

        int res = 0, cnt = 1;
        for (int i = 1; i <= n; i++)
            f[i] = i;

        for (int i = 1; i <= m; i++) {
            auto [a, b, c] = p[i];
            a = find(a), b = find(b);

            if (a != b)
                res += c, cnt++, f[a] = b;
        }

        if (cnt != n)
            cout << "impossible\n";
        else
            cout << res << "\n";
    }