题解 | #【模板】最小生成树#

题目链接

【模板】最小生成树

题目描述

给定一张包含 $n$ 个顶点、 $m$ 条无向加权边的连通图，边权为整数。请你求出该图的最小生成树（MST）：选出 $n-1$ 条边使其连通所有顶点且边权和最小。

需要输出：

第一行：MST 的边权总和；
第二行： $n-1$ 个互不相同的整数，表示所选边的编号（编号从 $1$ 开始，边编号按输入次序定义）。若 MST 不唯一，可输出任意一种方案。

解题思路

Kruskal + 并查集：将所有边按边权从小到大排序，依次尝试加入生成树；若当前边两端点不在同一连通块，则合并并将其计入答案。
并查集（DSU）：维护每个顶点所在连通块，支持 $\text{find}$ 与 $\text{union}$ （路径压缩 + 按秩/按大小合并）。
正确性：Kruskal 依据“切割性质/贪心选择”保证每一步选择的都是当前可行的最小边，最终得到的生成树权值最小。
实现细节：
- 记录边的输入编号 $\text{id}$ ，在挑中边时保存其 $\text{id}$ ；输出时可按挑选顺序输出（评测允许任意一组 MST）。
- 使用 64 位整型累计权值和。
复杂度：排序耗时 $\mathcal{O}(m\cdot \log m)$ ，并查集合并近似 $\mathcal{O}(m\cdot \alpha(n))$ ，总复杂度 $\mathcal{O}(m\cdot \log m)$ ；空间 $\mathcal{O}(n+m)$ 。

代码

c++
java
python

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

struct Edge {
    int u, v, id;
    long long w;
};

struct DSU {
    vector<int> parent, size;
    DSU(int n = 0) { init(n); }
    void init(int n) {
        parent.resize(n + 1);
        size.assign(n + 1, 1);
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a; size[a] += size[b];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<Edge> edges; edges.reserve(m);
    for (int i = 1; i <= m; ++i) {
        int u, v; long long w; cin >> u >> v >> w;
        edges.push_back({u, v, i, w});
    }
    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){
        if (a.w != b.w) return a.w < b.w;
        return a.id < b.id; // 同权时按编号稳定
    });

    DSU dsu(n);
    long long total = 0;
    vector<int> used;
    used.reserve(n - 1);
    for (const auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            total += e.w;
            used.push_back(e.id);
            if ((int)used.size() == n - 1) break;
        }
    }

    cout << total << '\n';
    for (int i = 0; i < (int)used.size(); ++i) {
        if (i) cout << ' ';
        cout << used[i];
    }
    cout << '\n';
    return 0;
}

import java.util.*;

public class Main {
    static class Edge {
        int u, v, id; long w;
        Edge(int u, int v, long w, int id) { this.u=u; this.v=v; this.w=w; this.id=id; }
    }
    static class DSU {
        int[] parent, size;
        DSU(int n) {
            parent = new int[n + 1];
            size = new int[n + 1];
            for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; }
        }
        int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
        boolean unite(int a, int b) {
            a = find(a); b = find(b);
            if (a == b) return false;
            if (size[a] < size[b]) { int t=a; a=b; b=t; }
            parent[b] = a; size[a] += size[b];
            return true;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Edge[] edges = new Edge[m];
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            long w = sc.nextLong();
            edges[i] = new Edge(u, v, w, i + 1);
        }
        Arrays.sort(edges, (a, b) -> {
            if (a.w != b.w) return Long.compare(a.w, b.w);
            return Integer.compare(a.id, b.id);
        });
        DSU dsu = new DSU(n);
        long total = 0;
        ArrayList<Integer> used = new ArrayList<>();
        for (Edge e : edges) {
            if (dsu.unite(e.u, e.v)) {
                total += e.w;
                used.add(e.id);
                if (used.size() == n - 1) break;
            }
        }
        System.out.println(total);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < used.size(); i++) {
            if (i > 0) sb.append(' ');
            sb.append(used.get(i));
        }
        System.out.println(sb);
    }
}

def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def unite(parent, size, a, b):
    a = find(parent, a)
    b = find(parent, b)
    if a == b:
        return False
    if size[a] < size[b]:
        a, b = b, a
    parent[b] = a
    size[a] += size[b]
    return True

n, m = map(int, input().split())
edges = []
for i in range(1, m + 1):
    u, v, w = map(int, input().split())
    edges.append((w, i, u, v))

edges.sort()  # 先按权重，再按编号
parent = [i for i in range(n + 1)]
size = [1] * (n + 1)
total = 0
used = []
for w, idx, u, v in edges:
    if unite(parent, size, u, v):
        total += w
        used.append(idx)
        if len(used) == n - 1:
            break

print(total)
print(' '.join(map(str, used)))

算法及复杂度

算法：Kruskal 算法，边权升序扫描 + 并查集合并，记录选中边的编号。
时间复杂度： $\mathcal{O}(m\cdot \log m)$ 。
空间复杂度： $\mathcal{O}(n+m)$ 。