InoueMoby's Blog

前言

你是一个城市规划师。 $N$ 座城市需要用公路连通——每座城市都能到达其他任何城市。你有 $M$ 条候选公路的设计方案，每条有不同的造价。问题是：用最少的钱把所有城市连通。

“连通”不等于”两两直通”。 $N=4$ 座城市只需要 3 条公路就能全连通（像一棵树），而不是 $4 \times 3 / 2 = 6$ 条。选出来的 $N-1$ 条边不包含任何环——这就是为什么叫”树”。

上一章的 Dijkstra 关心的是”从 A 到 B 的最短路径”。MST 关心的完全不同——它要的是”让整张图连通的总代价最小”。一个关注两点之间，一个关注全局最优。

最惊人的是，MST 有一个简单到不像话的贪心解法：把所有边按代价从小到大排序，从便宜的开始选。选的时候检查——如果两端已经连通了（会形成环），就跳过；否则就选。这就是 Kruskal 算法。它为什么是对的？为什么”先选便宜的”永远不会犯错？这正是本文要回答的核心问题。

问题的本质

MST 和最短路有什么区别？

初学者经常混淆 MST 和最短路，但它们的优化目标完全不同：

最短路（Dijkstra）：从起点 $s$ 到终点 $t$ ，找一条总权最小的路径。只关心两个点之间。
MST：选 $N-1$ 条边，让整张图连通，且总权最小。关心全局。

一个具体的例子：3 个节点，边 1-2(1)、2-3(1)、1-3(3)。

MST 选 1-2(1) + 2-3(1)，总权 = 2
最短路 1→3 走 1-2-3 = 2

看起来一样？换一组权重：1-2(1)、2-3(1)、1-3(1.5)。

MST 还是选 1-2(1) + 2-3(1)，总权 = 2
最短路 1→3 直走 1-3 = 1.5

MST 中从 1 到 3 的路径长度是 2，但实际最短路只有 1.5。MST 不保证任意两点间的路径最短——它只保证”选出来的边”的总权最小。

“先选便宜的”为什么不会犯错？——割性质（Cut Property）

Kruskal 的策略是”从最便宜的边开始选”。直觉上这有道理，但我们需要严格的保证：贪心选的边一定是某个 MST 中的边。

这需要割性质：

割性质：把图分成两半（割 $S$ 和 $T$ ），所有跨越割的边中，最短的那条 $e$ 一定属于某个 MST。

为什么？ 交换论证。假设最短跨越边 $e$ （权 $w$ ）不在 MST 中。但 MST 中一定有另一条边 $e'$ 也跨越同一个割（否则 $S$ 和 $T$ 不连通）。由于 $e$ 是最短的， $w(e) \le w(e')$ 。把 $e'$ 换成 $e$ ，总权不增，仍然是 MST。

Kruskal 每次选最短的、不形成环的边。选这条边时，它的两个端点分别在两个不同的连通块里——这恰好构成一个割。而这条边是所有跨越这个割的未选边中最短的（因为所有更短的边要么已经选了，要么被跳过了）。所以由割性质，这条边一定属于某个 MST。贪心永远不会犯错。

环检测为什么用并查集？

“加入边 $(u,v)$ 会形成环吗”等价于” $u$ 和 $v$ 是否已经连通”。并查集的 find 在 $O(\alpha(n))$ 时间内回答这个问题。

为什么不用 DFS/BFS？ 可以，但每加一条边就要跑一次 BFS，总时间 $O(M(N+M))$ 。并查集用路径压缩 + 按秩合并， $M$ 次查询总时间接近 $O(M)$ 。

教材的另一种理解：最大生成树

教材（Tessoku Book 9.7 B67 Max MST）提供了一个巧妙的观察：最大生成树可以转化为最小生成树。

具体方法：把每条边的权 $c$ 换成 $W - c$ （ $W$ 是一个足够大的常数），然后对新图跑最小生成树。选出来的边和原图完全一样，只是总权从 $\sum c$ 变成了 $(N-1)W - \sum c$ 。总权最小 $\Leftrightarrow$ 原图总权最大。

这意味着你只需要实现一种 MST 算法（Kruskal），然后通过变换就能同时处理最大/最小生成树。实际操作更简单——只需把排序改成从大到小。

两种算法：Kruskal vs Prim

	Kruskal	Prim
核心思路	按边权排序，贪心选边	从一个点扩展，每次选最短连出边
数据结构	并查集	优先队列（堆）
适合图	稀疏图（ $M \ll N^2$ ）	稠密图（ $M \approx N^2$ ）
时间复杂度	$O(M \log M)$	$O((N+M) \log N)$
比赛使用频率	★★★★★	★★★

竞赛中 90% 的 MST 题用 Kruskal 就够了，因为大部分图的边数远小于 $N^2$ 。

理论 + 代码

Kruskal 算法

Kruskal 的流程可以概括为三步：

把所有边按权值从小到大排序
依次尝试每条边，用并查集判断两端是否已连通
不连通就选入，连通就跳过

#include <cstdio>
#include <algorithm>
using namespace std;

struct Edge { int u, v, c; };
bool cmp(const Edge& a, const Edge& b) { return a.c < b.c; } // ① 按权排序

const int MAXN = 100006;
Edge edges[MAXN];
int parent[MAXN], rnk[MAXN];

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]); // ② 路径压缩
    return parent[x];
}

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rnk[rx] < rnk[ry]) parent[rx] = ry;        // ③ 按秩合并
    else if (rnk[rx] > rnk[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rnk[rx]++; }
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++)
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].c);
    sort(edges, edges + M, cmp);                     // ④ 排序
    for (int i = 1; i <= N; i++) { parent[i] = i; rnk[i] = 0; } // ⑤ 初始化并查集
    long long total = 0;
    int cnt = 0;
    for (int i = 0; i < M && cnt < N - 1; i++) {
        int u = edges[i].u, v = edges[i].v;
        if (find(u) != find(v)) {                    // ⑥ 不在同一连通块
            unite(u, v);                              // ⑦ 合并
            total += edges[i].c;                      // ⑧ 累加
            cnt++;
        }
    }
    printf("%lld\n", total);
    return 0;
}

逐行解析：

① cmp 按边权从小到大排序——这是 Kruskal 的核心：贪心先选便宜的。
② 并查集的路径压缩：find 沿路把所有节点直接挂到根上，后续查询 $O(1)$ 。为什么路径压缩如此重要？因为 Kruskal 要调用 $M$ 次 find，每次 $O(N)$ 的话总时间 $O(MN)$ ，超时。路径压缩后均摊 $O(\alpha(N))$ ，接近常数。
③ 按秩合并：小树挂到大树下面，防止树退化成链。和路径压缩一起使用，单次操作均摊 $O(\alpha(N))$ 。
④ 排序 $O(M \log M)$ ，这是 Kruskal 的时间瓶颈。
⑥ find(u) != find(v)： $u$ 和 $v$ 在不同连通块 → 加入这条边不会形成环。为什么加入连通的边会形成环？因为连通意味着 $u$ 和 $v$ 之间已经有一条路径，再加一条边就多了一条路径，形成闭合环。
⑦⑧ 选入这条边，合并两个连通块，累加权值。

走一遍具体过程

7 个节点、9 条边：

边	u	v	权
1	1	3	10
2	1	2	12
3	3	4	1
4	3	5	3
5	2	3	4
6	2	4	14
7	6	7	4
8	5	6	15
9	4	7	12

按权排序：3(1), 4(3), 5(4), 7(4), 1(10), 2(12), 9(12), 6(14), 8(15)

步骤	边	u-v	权	连通块状态	find(u)=find(v)?	操作	total	cnt
1	3	3-4	1	各自独立	不同	选入	1	1
2	4	3-5	3	{3,4}, {5}	不同	选入	4	2
3	5	2-3	4	{2}, {3,4,5}	不同	选入	8	3
4	7	6-7	4	{6}, {7}	不同	选入	12	4
5	1	1-3	10	{1}, {2,3,4,5}	不同	选入	22	5
6	2	1-2	12	{1,2,3,4,5}	相同	跳过	22	5
7	9	4-7	12	{1,..,5}, {6,7}	不同	选入	34	6

选满 $N-1=6$ 条边，MST 总权 = 34。

注意第 6 步：边 2 连接 1 和 2，但 find(1)=find(2)（它们已经在同一个连通块 {1,2,3,4,5} 中），所以跳过。如果强行加入，就会形成环——这条边是多余的。

Prim 算法（补充）

Kruskal 从”边”出发。Prim 从”点”出发：从一个节点开始，每次选”与当前生成树相连的最短边”加入。

想象你在建地铁网：先确定第一个站点，然后每次在已有的网络边界上找一个”最近的未连通站点”，修一条地铁线过去。

// Prim 简易版 O(N²)，适合稠密图
int mincost[MAXN]; // 每个节点到生成树的最短边权
bool used[MAXN];
long long prim(int N) {
    long long total = 0;
    memset(mincost, 0x3f, sizeof(mincost));
    memset(used, false, sizeof(used));
    mincost[1] = 0;
    for (int i = 0; i < N; i++) {
        int u = -1;
        for (int v = 1; v <= N; v++)
            if (!used[v] && (u == -1 || mincost[v] < mincost[u])) u = v;
        used[u] = true;
        total += mincost[u];
        for (auto [v, w] : adj[u])
            mincost[v] = min(mincost[v], w);
    }
    return total;
}

逐行解析：

mincost[v] 维护节点 $v$ 到当前生成树的最短边权。初始化为 $\infty$ ，只有起点为 0。
每轮找 mincost 最小的未使用节点 $u$ ，把它加入生成树。
加入 $u$ 后，更新 $u$ 的所有邻居的 mincost。

朴素版 $O(N^2)$ 。用堆优化（优先队列维护 mincost）可以降到 $O((N+M) \log N)$ ，和 Kruskal 同阶。但竞赛中通常直接用 Kruskal，因为更短、更不容易写错。

最大生成树：只需改一个符号

教材 B67 Max MST 的核心观察：最大生成树和最小生成树用的是同一个算法，只是排序方向相反。

bool cmp(const Edge& a, const Edge& b) { return a.c > b.c; } // 从大到小

其余代码完全不变。为什么这也是对的？因为割性质的对称版本：跨越割的最长边一定在某个最大生成树中。或者用教材的变换理解：把权 $c$ 换成 $W-c$ 后，最大生成树变成了最小生成树。

例题

例题 1：TB A67 — MST

题目： $N$ 个顶点 $M$ 条加权无向图。求最小生成树的边权总和。

数据范围： $2 \le N \le 10^5$ ， $1 \le M \le 10^5$ ， $1 \le C_i \le 10000$

—— AtCoder Tessoku Book A67

分析：Kruskal 模板。按边权排序，并查集判环。

样例输入：N=7, M=9，边 (1,2,12), (1,3,10), (2,6,160), (2,7,15), (3,4,1), (3,5,4), (4,5,3), (4,6,120), (6,7,14)。输出：55。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

struct Edge { int u, v, c; };
const int MAXN = 100006;
Edge edges[MAXN];
int parent[MAXN], rnk[MAXN];

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

void unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return;
    if (rnk[rx] < rnk[ry]) parent[rx] = ry;
    else if (rnk[rx] > rnk[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rnk[rx]++; }
}

int main() {
    int N, M;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++)
        scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].c);
    sort(edges, edges + M, [](const Edge& a, const Edge& b) { return a.c < b.c; }); // ① 排序
    for (int i = 1; i <= N; i++) { parent[i] = i; rnk[i] = 0; }
    long long total = 0;
    int cnt = 0;
    for (int i = 0; i < M && cnt < N - 1; i++) {
        if (find(edges[i].u) != find(edges[i].v)) { // ② 不在同一连通块
            unite(edges[i].u, edges[i].v);
            total += edges[i].c;
            cnt++;
        }
    }
    printf("%lld\n", total);
    return 0;
}

逐行解析：

① 按边权从小到大排序——Kruskal 的贪心核心。
② find(u) != find(v)：两端不连通，加入不形成环。

模拟：排序后 3-4(1), 4-5(3), 3-5(4), 1-3(10), 1-2(12), 6-7(14), 2-7(15), 4-6(120), 2-6(160)。

步骤	边	权	连通块变化	选?
1	3-4	1	{3,4}	✅
2	4-5	3	{3,4,5}	✅
3	3-5	4	已连通	❌
4	1-3	10	{1,3,4,5}	✅
5	1-2	12	{1,2,3,4,5}	✅
6	6-7	14	{6,7}	✅
7	2-7	15	全部合并	✅

total = 1+3+10+12+14+15 = 55。✓

例题 2：TB B67 — Max MST

题目：同一张图，求最大生成树。

—— AtCoder Tessoku Book B67

分析：教材 9.7 的核心技巧——排序方向取反即可。割性质的对称版本保证了正确性。

代码（与例题 1 唯一区别）：

sort(edges, edges + M, [](const Edge& a, const Edge& b) { return a.c > b.c; }); // 从大到小

模拟：排序后 2-6(160), 4-6(120), 2-7(15), 6-7(14), 1-2(12), 1-3(10), 3-5(4), 4-5(3), 3-4(1)。

步骤	边	权	选?
1	2-6	160	✅
2	4-6	120	✅
3	2-7	15	✅
4	6-7	14	❌ (6,7 已连通)
5	1-2	12	✅
6	1-3	10	✅
7	3-5	4	✅

total = 160+120+15+12+10+4 = 321。

例题 3：T90 003 — Longest Circular Road

题目： $N$ 个城镇的树（ $N-1$ 条道路）。从某城镇出发走一圈回来，最多经过几个不同城镇？

—— AtCoder Typical 90 003

分析：树的直径问题。树上无环，走一圈 = 沿直径走过去再回来，经过的不同城镇数 = 直径长度 + 1。两次 BFS 找直径端点。

代码：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 100006;
vector<int> adj[MAXN];
int dist[MAXN];

int bfs_farthest(int start) {
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[start] = 0; q.push(start);
    int far = start;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                if (dist[v] > dist[far]) far = v; // ① 记录最远点
                q.push(v);
            }
        }
    }
    return far;
}

int main() {
    int N; scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int a, b; scanf("%d%d", &a, &b);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    int a = bfs_farthest(1);  // ② 第一次 BFS
    int b = bfs_farthest(a);  // ③ 第二次 BFS
    printf("%d\n", dist[b] + 1); // ④ 节点数 = 距离 + 1
}

逐行解析：

① 每发现新节点就更新最远点。
②③ 两次 BFS 找直径端点。从任意节点出发的最远点一定是直径端点之一——这是树的特殊性质。
④ 直径长度 dist[b]，经过的城镇数 = 边数 + 1。

例题 4：T90 039 — Tree Distance

题目： $N$ 个节点的树，对每个节点 $k$ ，求 $k$ 到所有其他节点的距离之和。

—— AtCoder Typical 90 039

分析：朴素 $O(N^2)$ 对每个节点 BFS 会超时。换根 DP 可以 $O(N)$ 解决。

先以 1 为根算 ans[1] 和每个子节点子树大小 subsize[v]。当根从 $u$ 变为子节点 $v$ 时： $v$ 的子树里 subsize[v] 个节点距离减 1，其余 N - subsize[v] 个节点距离加 1。所以 $ans[v] = ans[u] + N - 2 \cdot subsize[v]$ 。

代码：

#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 100006;
vector<int> adj[MAXN];
long long ans[MAXN];
int subsize[MAXN], N;

void dfs1(int u, int p, int depth) {
    ans[1] += depth;
    subsize[u] = 1;
    for (int v : adj[u])
        if (v != p) { dfs1(v, u, depth + 1); subsize[u] += subsize[v]; }
}

void dfs2(int u, int p) {
    for (int v : adj[u])
        if (v != p) {
            ans[v] = ans[u] + N - 2 * subsize[v]; // ① 换根公式
            dfs2(v, u);
        }
}

int main() {
    scanf("%d", &N);
    for (int i = 0; i < N - 1; i++) {
        int a, b; scanf("%d%d", &a, &b);
        adj[a].push_back(b); adj[b].push_back(a);
    }
    dfs1(1, 0, 0);  // ② 算 ans[1] 和 subsize
    dfs2(1, 0);      // ③ 换根传递
    for (int i = 1; i <= N; i++) printf("%lld\n", ans[i]);
}

逐行解析：

① 换根公式： $v$ 的子树节点离新根近了 1（减 subsize[v]），其余节点远了 1（加 N - subsize[v]）。
② 第一次 DFS：累加深度得到 ans[1]，同时计算每个子树的大小。
③ 第二次 DFS：用换根公式从父节点推子节点。

参考文献

教材讲解 — 競技プログラミングの鉄則第 9 章

9.7 最大生成木（B67 Max MST 解说）

基础练习 — アルゴリズムと数学演習問題集

048 Small Multiple（01-BFS）

系统练习 — 競技プログラミングの鉄則

实战练习 — 競プロ典型 90 問

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

最小生成树

用最小的代价连通所有城市——Kruskal 的贪心排序和并查集判环，Prim 的堆优化

前言

问题的本质

MST 和最短路有什么区别？

“先选便宜的”为什么不会犯错？——割性质（Cut Property）

环检测为什么用并查集？

教材的另一种理解：最大生成树

两种算法：Kruskal vs Prim

理论 + 代码

Kruskal 算法

走一遍具体过程

Prim 算法（补充）

最大生成树：只需改一个符号

例题

例题 1：TB A67 — MST

例题 2：TB B67 — Max MST

例题 3：T90 003 — Longest Circular Road

例题 4：T90 039 — Tree Distance

参考文献

系列索引

最小生成树