最小生成树

MST(Minimum Spanning Tree)

Posted by Marlin on August 22, 2025

最小生成树

概念

  • 生成树:n 个点、n-1 条边,连通且无环。
  • 最小生成树 MST:边权总和最小的生成树。
  • 最小瓶颈树: 所有生成树中最大边权最小的树。最小瓶颈树一定是 MST。

Kruskal(边排序 + 并查集)

复杂度

  • 排序:$O(m log m)$
  • 并查集:$O(m α(n)) + O(n)$
  • 总:$O(m log m) + O(n)$。 稀疏图首选。

思路:

  • 先将所有边按权值排序。
  • 重复以下操作:
    • 选择一条最小权值的边 $(u, v, w)$。
    • 如果 $(u, v)$ 不在并查集中,则将 $(v, u, w)$ 加入并查集。
    • 否则,跳过该边。
  • 最后得到的生成树即为最小生成树。

代码

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
struct Edge {
    int u, v, w;
    bool operator<(const Edge& o) const { return w < o.w; }
};

struct DSU {
    vector<int> f;
    DSU(int n) : f(n) { iota(f.begin(), f.end(), 0); }
    int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        f[y] = x; return true;
    }
};

ll kruskal(int n, vector<Edge>& e) {
    sort(e.begin(), e.end());
    DSU dsu(n);
    ll sum = 0, cnt = 0;
    for (auto [u, v, w] : e) {
        if (dsu.unite(u, v)) {
            sum += w;
            if (++cnt == n - 1) break;
        }
    }
    return cnt == n - 1 ? sum : -1;   // -1 表示不连通
}

题目 1 最小生成树(Kruskal)

给定一个无向连通图,边有权值,求其最小生成树。

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
40
41
42
const int N = 1e6 + 10;
vector<int> fa(N);
void init(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        return false;
    }
    fa[fx] = fy;
    return true;
}
int n, m;
struct Edge {
    int u, v, w;
    bool operator<(Edge &o) { return w < o.w; }
};
void solve() {
    cin >> n >> m;
    vector<Edge> edges;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edges.push_back({u, v, w});
    }
    sort(edges.begin(), edges.end());
    init(n);
    int cnt = 0;
    int sum = 0;
    for (auto [u, v, w] : edges) {
        if (merge(u, v)) {
            cnt++;
            sum += w;
        }
    }
    cout << ((cnt == n - 1) ? to_string(sum) : "orz") << endl;
}

Prim(点扩展 + 优先队列)

复杂度

  • 二叉堆:O(m log n)
  • Fibonacci 堆(理论):O(m + n log n)
  • 一般用 priority_queue,O(m log n)。稠密图可转邻接矩阵暴力 O(n²) 版本。

思路

  • 选择一个源点,将其加入优先队列。
  • 重复以下操作:
    • 从优先队列中取出最小权值的边 $(u, v, w)$。
    • 如果 $(u, v)$ 未被访问过,则将 $(v, u, w)$ 加入优先队列。
    • 将 $(u, v)$ 标记为已访问。
  • 最后得到的生成树即为最小生成树。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using PII = pair<int,int>;

ll prim(int n, const vector<vector<PII>>& g) {
    vector<char> vis(n);
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.emplace(0, 0);          // {dist, node}
    ll sum = 0, cnt = 0;
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = 1; sum += d; ++cnt;
        for (auto [v, w] : g[u])
            if (!vis[v]) pq.emplace(w, v);
    }
    return cnt == n ? sum : -1;
}

题目 2 最小生成树(Prim)

给定一个无向连通图,边有权值,求其最小生成树。

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
int n, m;
struct MaxHeapCmp {
    bool operator()(const pair<int, int> &a, const pair<int, int> &b) const {
        return a.second > b.second;
    }
};
void solve() {
    cin >> n >> m;
    vector<vector<pair<int, int>>> g(n + 1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, MaxHeapCmp> heap;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for (auto edge : g[1]) {
        heap.push(edge);
    }
    vector<bool> set(n + 1);
    int nodeCnt = 1;
    set[1] = true;
    int ans = 0;
    while (!heap.empty()) {
        auto [v, w] = heap.top();
        heap.pop();
        if (!set[v]) {
            nodeCnt++;
            set[v] = true;
            ans += w;
            for (auto edge : g[v]) {
                heap.push(edge);
            }
        }
    }
    cout << ((nodeCnt == n) ? to_string(ans) : "orz");
}

题目 3 水资源分配优化

1
2
3
4
5
6
7
村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
对于每个房子 i,我们有两种可选的供水方案:一种是直接在房子内建造水井
成本为 wells[i - 1] (注意 -1 ,因为 索引从0开始 )
另一种是从另一口井铺设管道引水,数组 pipes 给出了在房子间铺设管道的成本,
其中每个 pipes[j] = [house1j, house2j, costj]
代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
请返回 为所有房子都供水的最低总成本

思路: 将井看做一个节点,将建井看做修村庄到井的路,管道看做修村庄间的路,则问题转化为求修出让所有村庄到井的路的最小代价

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
40
41
42
43
vector<int> fa;
void init(int n){
    fa.resize(n + 1);
    for(int i = 0; i <= n; i++){
        fa[i] = i;
    }
}
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool merge(int x, int y){
    int fx = find(x);
    int fy = find(y);
    if(fx == fy) {
        return false;
    }
    fa[fx] = fy;
    return true;
}
struct Edges {
    int u, v, w;
    bool operator<(const Edges& o) const {
        return w < o.w;
    }
};
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) { // wells为修井的成本,pipes为管道的成本
    init(n);
    vector<Edges> edges;
    for(int i = 0; i < n; i++){
        edges.push_back({0, i + 1, wells[i]}); // 0 代表水源点 i + 1为村庄编号 wells[i]为代价
    }
    for(int i = 0; i < pipes.size(); i++){
        edges.push_back({pipes[i][0], pipes[i][1], pipes[i][2]});
    }
    sort(edges.begin(), edges.end());
    int ans = 0;
    for(auto [u, v, w] : edges){
        if(merge(u, v)){
            ans += w;
        }
    }
    return ans; // 题目保证所有节点一定联通
}

题目 4 检查边长度限制的路径是否存在

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
40
41
42
43
44
45
46
47
vector<int> fa;
void init(int n) {
    fa.resize(n);
    for (int i = 0; i < n; i++) {
        fa[i] = i;
    }
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        return false;
    }
    fa[fx] = fy;
    return true;
}
bool isSameSet(int a, int b) { return find(a) == find(b); }
vector<vector<int>> questions;
vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>> &edges, vector<vector<int>> &queries){
    int m = edges.size();
    int k = queries.size();
    // 步骤1:绑定查询原始索引
    for (int i = 0; i < k; i++) {
        questions.push_back(
            {queries[i][0], queries[i][1], queries[i][2], i});
    }
    // 步骤2:双排序(边和查询都按限制值升序)
    sort(questions.begin(), questions.end(),
            [](vector<int> &a, vector<int> &b) { return a[2] < b[2]; });
    sort(edges.begin(), edges.end(),
            [](vector<int> &a, vector<int> &b) { return a[2] < b[2]; });
    // 步骤3:初始化并查集
    init(n);
    vector<bool> ans(k);
    // 步骤4:双指针处理
    for (int i = 0, j = 0; i < k; i++) { // i遍历查询,j遍历边
        // 合并所有边权小于当前查询限制的边
        while (j < m && edges[j][2] < questions[i][2]) {
            merge(edges[j][0], edges[j][1]);
            j++;
        }
        // 检查当前查询的连通性
        ans[questions[i][3]] = isSameSet(questions[i][0], questions[i][1]);
    }
    return ans;
}

题目 5 最小瓶颈树-繁忙的都市

最小瓶颈树

所有生成树中最大边权最小的树。

结论:MST 一定也是最小瓶颈树,反之不一定。因此直接跑 MST 即可。

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
40
41
42
const int N = 400;
int n, m;
vector<vector<pair<int, int>>> g(N);
vector<int> fa;
void init(int n) {
    fa.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
bool merge(int x, int y) {
    int fx = find(x);
    int fy = find(y);
    if (fx == fy) {
        return false;
    }
    fa[fx] = fy;
    return true;
}
struct edges {
    int u, v, w;
    bool operator<(const edges &o) { return w < o.w; }
};
void solve() {
    cin >> n >> m;
    vector<edges> edges;
    for (int i = 0; i < m; i++) {
        int uu, vv, ww;
        cin >> uu >> vv >> ww;
        edges.push_back({uu, vv, ww});
    }
    sort(edges.begin(), edges.end());
    init(n);
    int maxedge = -1;
    for (auto [u, v, w] : edges) {
        if (merge(u, v)) {
            maxedge = max(w, maxedge);
        }
    }
    cout << n - 1 << " " << maxedge << endl;
}