第 92 章 最小生成树¶
配套例题：BISHI107 【模板】最小生成树Ⅰ ‖ 稀疏图：Kruskal、BISHI104 修复公路 来源：S2
Kruskal.cpp、Prime.cpp；S4模板.docx「树 → 最小生成树 prime / kruskal / 次小生成树」；S3 day7 前置：38-并查集、90-图的表示与遍历、47-贪心
最小生成树是贪心正确性最漂亮的例子之一：随便按边权从小到大挑， 只要不成环就要，最后一定得到全局最优。这一章讲清楚它为什么对、 两种实现怎么选、以及 Python 下的写法。
92.1 定义¶
BISHI107 的题面给的定义就很标准：
生成树：对于一张 \(n\) 个节点的图，任选其中 \(n-1\) 条边，使得节点两两连通， 这些边一定会组成一棵树，称为这张图的一棵生成树。
最小生成树（MST）：权值和最小的生成树。
三个立刻要明确的前提：
| 前提 | 说明 |
|---|---|
| 无向图 | MST 只对无向图定义。有向图的对应物是「最小树形图」（朱刘算法），不在笔试范围 |
| 必须连通 | 不连通就没有生成树，题目通常要求输出 NO / \(-1\) |
| 边权可以是负数 | 贪心证明不依赖非负性。BISHI107 的 \(w\) 可以低到 \(-10^9\) |
⚠️ 「边权可以是负数」是个高频坑。写成「答案初始化为 0，只累加正边」 或者「跳过负边」都是错的：MST 要求恰好 \(n-1\) 条边把所有点连起来， 负边不但要选，还会优先被选。
92.2 为什么贪心是对的¶
切割性质（Cut Property）——Prim 的正确性¶
把点集任意划分成两个非空部分 \(S\) 和 \(V \setminus S\)， 横跨这条「切割」的所有边中权值最小的那条（若唯一）一定在每棵 MST 里。
证明（交换论证）：设最小横跨边是 \(e\)，假设某棵 MST \(T\) 不含 \(e\)。 把 \(e\) 加进 \(T\) 会形成一个环，这个环必然还包含另一条横跨边 \(f\)（要出去就得回来）。 由 \(w(e) \le w(f)\)，把 \(f\) 换成 \(e\) 得到的仍是生成树且权和不增， 所以存在含 \(e\) 的 MST；若 \(w(e) < w(f)\) 严格成立，则 \(T\) 不是最优，矛盾。
环性质（Cycle Property）——Kruskal 的正确性¶
任意一个环上权值最大的边（若唯一）一定不在任何 MST 里。
Kruskal 就是它的直接推论：按权升序考虑边，若当前边的两端已连通， 那么这条边加进去会成环，且它是环上最大的边（因为其余边都更早被选、权更小）， 所以可以安全丢弃。
由此得到的三条实用推论¶
| 推论 | 用途 |
|---|---|
| MST 上任意两点的路径，是所有路径中「最大边权最小」的 | 最小瓶颈路 = MST 上的路径（BISHI104） |
| 所有 MST 的边权多重集完全相同 | 判「MST 是否唯一」只需看每种权值被选的条数 |
| 边权全部互不相同 ⟹ MST 唯一 | 出题人常用这条来避免多解 |
92.3 Kruskal¶
S2 Kruskal.cpp 开头一行注释点明了适用范围：「适用于边较少的图」。
三步：① 所有边按权升序排序；② 依次尝试加入，用并查集判两端是否已连通； ③ 加满 \(n-1\) 条即得 MST。
def kruskal(n, edges):
"""Kruskal 最小生成树。edges = [(w, u, v), ...]，点编号 1..n。
返回 (总权值, 选中的边列表)；图不连通时返回 (None, ...)。
复杂度 O(m log m)，瓶颈是排序（C 层 Timsort）。
"""
edges.sort() # ★ w 放元组第一位，直接 sort()
# DSU（Disjoint Set Union，并查集）：唯一的作用是回答「这两点已经连通了吗」
parent = list(range(n + 1)) # 初始每个点自成一块，父亲是自己
size = [1] * (n + 1) # size[根] = 该块的点数，用于按大小合并
def find(x):
"""迭代路径压缩：两趟。递归版在 n = 3e5 的退化链上必爆栈。"""
r = x
while parent[r] != r: # 第一趟：一路向上找到根
r = parent[r]
while parent[x] != r: # 第二趟：把路上每个点直接挂到根下
parent[x], x = r, parent[x] # 右边先整体求值，再解包赋值
return r # 压缩之后这条链下次查询就是 O(1)
need = n - 1 # 还差几条边；n = 1 时开局就是 0
total = 0
chosen = []
for w, u, v in edges: # 按权升序考虑每条边（贪心的核心顺序）
if need == 0:
break # 已经选够，剩下的边不用看
ru, rv = find(u), find(v)
if ru == rv:
continue # 同一连通块 -> 加进去会成环，丢弃
# 由环性质，它是那个环上的最大边，丢弃安全
if size[ru] < size[rv]: # 按大小合并，让树更浅
ru, rv = rv, ru # 保证 ru 是较大的那块
parent[rv] = ru # 小块挂到大块下面
size[ru] += size[rv]
total += w # w 可能为负，照加不误
chosen.append((u, v, w))
need -= 1
return (total if need == 0 else None), chosen # 没选够 n-1 条 = 原图不连通
Python 的三个关键写法：
| 写法 | 理由 |
|---|---|
edges 存成 (w, u, v) 后直接 sort() |
比 sort(key=lambda e: e[2]) 少 \(m\) 次 Python 函数调用，\(m=3\times10^5\) 时差别巨大 |
find 用迭代路径压缩 |
递归在退化链上必爆 C 栈（无报错的段错误），见 38 章 |
if need == 0: break |
选满就停，省掉后面所有 find |
性能上界：Kruskal 的瓶颈是排序，而 Python 的
sort()是 C 层 Timsort， \(3\times10^5\) 条边只要 0.3 秒左右。并查集部分才是纯 Python 循环， 所以要尽量把find写得便宜（路径压缩 + 按大小合并）。
92.4 Prim¶
S2 Prime.cpp 和 S4 的模板都是邻接矩阵 + \(O(n^2)\) 的朴素版：
for(int i=1; i<=n; i++) dis[i]=map[1][i];
vis[1]=1;
for(int i=1; i<=n-1; ++i) {
int minn=0x3f3f3f3f;
for(int j=1; j<=n; ++j) if(!vis[j]&&dis[j]<minn) minn=dis[j],pos=j;
vis[pos]=1; sum+=dis[pos];
for(int j=1; j<=n; ++j)
if(!vis[j]&&dis[j]>map[pos][j]) dis[j]=map[pos][j];
}
思想：维护一个已在树中的点集 \(S\)（初始只有 1 号点），
dis[j] 表示「\(j\) 到 \(S\) 的最短边权」。每轮取 dis 最小的点加入 \(S\)，
再用它更新其余点的 dis。这就是切割性质的直接应用。
注意 Prim 和 Dijkstra 的差别只有一行： Dijkstra 松弛写
dis[v] = min(dis[v], dis[u] + w)（到源点的距离）， Prim 写dis[v] = min(dis[v], w)（到集合的距离）。 结构完全一样，所以 Prim 也能堆优化。
朴素 \(O(n^2)\) Prim（稠密图）¶
def prim_dense(g, n):
"""朴素 O(n^2) Prim，邻接矩阵版。稠密图 + n <= 1500 时用。
g[i][j] 是边权，不通为 INF（大整数）。返回 (总权值, 是否连通)。
"""
INF = 1 << 60
dis = g[1][:] # dis[j] = j 到当前树的最短边
# 树里只有 1 号点，所以初值就是 1 到 j 的边
dis[1] = 0
used = bytearray(n + 1) # used[j] = 1 表示 j 已经在树里
used[1] = 1 # 从 1 号点起步（从哪个点起都一样）
total = 0
for _ in range(n - 1): # 每轮往树里加一个点，共加 n-1 个
best = INF
pos = -1
for j in range(1, n + 1): # 找树外最近的点
if not used[j] and dis[j] < best:
best = dis[j]
pos = j
if pos < 0:
return None, False # 树外的点全都够不着 -> 图不连通
used[pos] = 1 # 由切割性质，这条最小横跨边一定在 MST 里
total += best
gp = g[pos] # 绑成局部名
for j in range(1, n + 1): # 用新加入的点更新 dis
if not used[j] and gp[j] < dis[j]:
dis[j] = gp[j] # 注意是 min(dis[j], 边权)，不加 dis[pos]
return total, True # 与 Dijkstra 的差别就在上面这一行
堆优化 Prim（稀疏图）¶
from heapq import heappush, heappop
def prim_heap(n, start, to, wt, root=1):
"""堆优化 Prim（CSR 邻接表版）。O(m log m)。
和 Dijkstra 的唯一区别：入堆的键是**边权本身**，不是累计距离。
同样用懒删除处理堆里的过期记录。
"""
used = bytearray(n + 1) # used[u] = 1 表示 u 已进树
total = 0
cnt = 0 # 已进树的点数
heap = [(0, root)] # (把 u 接进树的边权, u)；根的接入代价记 0
while heap:
w, u = heappop(heap) # 全堆最小 = 当前切割上的最小横跨边
if used[u]: # 懒删除：这个点已经进树了
continue # 堆里同一个点会有多份，只认第一份
used[u] = 1
total += w # 只有真正进树时才把边权计入答案
cnt += 1
for i in range(start[u], start[u + 1]):
v = to[i]
if not used[v]:
heappush(heap, (wt[i], v)) # ★ 键是边权本身，不是累计距离
return (total, True) if cnt == n else (None, False) # 没收满 n 个点 = 不连通
92.5 Kruskal vs Prim：怎么选¶
| Kruskal | 朴素 Prim | 堆优化 Prim | |
|---|---|---|---|
| 复杂度 | \(O(m \log m)\) | \(O(n^2)\) | \(O(m \log m)\) |
| 需要的存图方式 | 边表（不用建邻接表！） | 邻接矩阵 | 邻接表 / CSR |
| 稀疏图 \(m \approx n\) | ✅ 最佳 | ❌ 浪费 | ✅ 可以 |
| 稠密图 \(m \approx n^2\) | ⚠️ 排序 \(n^2\) 条边 | ✅ 最佳 | ❌ 堆里 \(n^2\) 个元素 |
| 边直接给出、点数很大 | ✅ | ❌ | ⚠️ |
| Python 实现难度 | 最低（排序 + 并查集） | 低 | 中 |
| Python 常数 | 最小（排序在 C 层） | 中（纯循环） | 大（堆操作） |
Python 选手的默认答案是 Kruskal。理由： ① 主要开销
sort()落在 C 层； ② 只需要边表，省掉建邻接表的时间和内存； ③ 并查集是全竞赛常数最小的数据结构之一。只有在「\(n \le 1000\) 且给的是邻接矩阵 / 完全图（比如平面上 \(n\) 个点两两连边）」 时才该换朴素 Prim——那时候边数是 \(n^2/2\)，排序它反而更慢。
92.6 次小生成树¶
S4 的模板清单里列了「次小生成树」，但正文是空的（原文标注「暂时没有」）。 这里补上。
两种口径，读题时必须分清：
| 口径 | 定义 | 做法 |
|---|---|---|
| 非严格次小 | 权和 \(\le\) MST 的次优生成树（可以等于） | 枚举非树边，减去路径最大边 |
| 严格次小 | 权和严格大于 MST 的最小生成树 | 还要维护路径次大边 |
核心定理：次小生成树与 MST 恰好只差一条边。
于是算法是：先求 MST，然后枚举每条非树边 \((u,v,w)\)， 把它加进 MST 会形成一个环，从环上（也就是 MST 上 \(u \to v\) 的路径上） 删掉一条边，权和变化量是 \(w - (\text{路径上被删边的权})\)。 要让增量最小，就删路径上权值最大的边； 若该最大边恰好等于 \(w\)（增量为 0，得到的是另一棵 MST）， 求严格次小时就得退而求其次，删路径上小于 \(w\) 的最大边（即次大边）。
用倍增在 MST 上预处理「向上 \(2^k\) 步的路径最大边和次大边」：
# [片段] 次小生成树：MST + 倍增维护路径最大/次大边
# 前置：已用 Kruskal 求出 MST（chosen 列表）与总权 total，且图连通
from collections import deque
LOG = 18 # 2^18 > 2.6e5，按 n 调整
NEG = -1 << 60 # 「不存在」的哨兵
# 1) 用 MST 的边建树（CSR 或 list of list 都行），BFS 求 depth / parent
# 2) 倍增表：up[k][v] = v 向上 2^k 步的祖先
# mx[k][v] = 这段路径上的最大边权
# se[k][v] = 严格小于 mx 的最大边权（次大）
def merge(a1, a2, b1, b2):
"""合并两段的 (最大, 次大)。次大必须严格小于最大。"""
mx = a1 if a1 > b1 else b1 # 两段最大值里再取大的
cands = [x for x in (a1, a2, b1, b2) if x < mx] # 只留严格小于 mx 的候选
se = max(cands) if cands else NEG # 四个值全相等时次大不存在，返回哨兵
return mx, se
# 3) 查询：把 u、v 提到同深度再一起上跳，沿途 merge，得到路径 (最大, 次大)
# 4) 枚举每条非树边 (u, v, w)：
# mx, se = path_max(u, v)
# if w > mx: cand = total + w - mx # 严格次小
# elif se > NEG and w > se: cand = total + w - se
# 取所有 cand 的最小值
复杂度：\(O(m \log m + n \log n + m \log n)\)。
Python 的现实性判断：倍增表是 \(18 \times n\) 的三张表。 \(n = 10^5\) 时是 \(5.4\times10^6\) 个表项，光建表就要 5 秒以上，内存也上百 MB。 结论：次小生成树在 Python 下的现实规模是 \(n \le 2\times10^4\)。 更大规模要么换语言，要么用「按秩合并的可撤销并查集 + 离线」之类的技巧规避倍增表。 倍增的通用讨论见 45-倍增。
92.7 MST 的常见变形¶
| 变形 | 做法 |
|---|---|
| 最小瓶颈生成树 | 就是 MST（最大边最小）。「最早何时全连通」类题（BISHI104）直接跑 Kruskal 取最大边 |
| 最大生成树 | 边权降序排序，Kruskal 照跑 |
| 必须包含某些边 | 先把这些边无条件合并，再对剩下的跑 Kruskal |
| MST 是否唯一 | 对每种权值，统计「这批边加进来时减少了几个连通块」，若某种权值存在多种选法则不唯一 |
| 两点间最小瓶颈路 | 建出 MST 后，答案 = MST 上两点路径的最大边（倍增 / 树剖，见 94 章） |
| 动态加边维护 MST | 每加一条边，在环上删最大边（LCT 领域，超纲） |
| 点数少、边是坐标算出来的 | 完全图 \(m = n^2/2\)，用朴素 Prim |
Borůvka 算法（每轮为每个连通块找一条最小出边）值得知道名字： 它是唯一天然可并行的 MST 算法，也是「最小异或生成树」等 Trie 类题的基础。 笔试范围内用不到。
92.8 例题¶
BISHI107 【模板】最小生成树Ⅰ ‖ 稀疏图：Kruskal（较难）¶
\(n, m \le 3\times10^5\) 的无向赋权图（可能不连通、可能有重边、无自环）， \(-10^9 \le w \le 10^9\)。图不连通输出
NO，否则输出 MST 边权和。 时限：C/C++ 5 秒，其他语言 10 秒。 题面见 BISHI107 原题（牛客）。 题解见solutions/BISHI107.py（已用官方样例验证）。
标题就写明了「稀疏图：Kruskal」。\(m\) 与 \(n\) 同阶，Kruskal 是最优选择。
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
edges = [None] * m # 预分配，避免 append 扩容
p = 2
for i in range(m):
u = int(data[p]); v = int(data[p + 1]); w = int(data[p + 2]); p += 3
edges[i] = (w, u, v) # 权值放首位，sort() 即按权升序
edges.sort() # 唯一的排序，C 层 Timsort
parent = list(range(n + 1)) # 并查集：初始每个点自成一块
size = [1] * (n + 1) # 按大小合并，避免树退化成链
def find(x):
r = x
while parent[r] != r: # 先一路向上找到块的根
r = parent[r]
while parent[x] != r: # 迭代路径压缩
parent[x], x = r, parent[x] # 把沿途的点全部改挂到根上
return r
need = n - 1 # 还差几条边；n = 1 时开局就是 0
total = 0
for w, u, v in edges: # 贪心：按权从小到大依次尝试
if need == 0:
break # 已经选够 n-1 条，后面的边不必再看
ru, rv = find(u), find(v)
if ru == rv:
continue # 已连通，这条边会成环
if size[ru] < size[rv]:
ru, rv = rv, ru # 让 ru 指向较大的块
parent[rv] = ru # 合并两块
size[ru] += size[rv]
total += w # w 可能为负，照加不误
need -= 1
sys.stdout.write(("%d\n" % total) if need == 0 else "NO\n") # 没选够 = 不连通
main()
复杂度：排序 \(O(m\log m) \approx 3\times10^5 \times 18\)（C 层）， 并查集近似线性。\(m = 3\times10^5\) 在 10 秒时限下很轻松。
三个坑：
- 边权可以是负数（样例 2 里有 \(-12\)）。这不影响 Kruskal 的正确性—— 贪心的证明不依赖非负性——但答案可能是负数， 所以不能写「答案初始化为 0 且只加正数」之类的偷懒逻辑；
- \(n = 1\) 时答案是 0，且图算连通。上面代码里
need = n - 1 = 0， 循环第一次就break，输出0✓。写成「必须选够 \(n-1\) 条边否则 NO」时， 要保证 \(n=1\) 落在「选够了」这一侧； - 有重边，Kruskal 天然处理（同根跳过），不必预处理去重。
为什么不用 Prim？ \(m = 3\times10^5\)、\(n = 3\times10^5\)，是典型稀疏图。 堆优化 Prim 的堆里会塞进 \(6\times10^5\) 个元组，比 Kruskal 的一次排序慢得多； 朴素 Prim 是 \(O(n^2) = 9\times10^{10}\)，直接出局。
Python 现实性判断：\(3\times10^5\) 条边的元组构造 +
sort()约 1 秒， 主循环是 \(3\times10^5\) 轮 × 2 次find（每次几步 while），约 \(3\times10^6\) 次迭代， 约 2 秒。10 秒时限留有余量。若要再压：把find内联进主循环 （见 38 章 的扁平数组版）。
BISHI104 修复公路（中等）¶
\(N \le 10^3\) 个城市、\(M \le 10^5\) 条双向公路，第 \(i\) 条连接 \(x_i, y_i\) 且在第 \(t_i\) 秒修完（\(1 \le t \le 10^5\)）。 问最早何时任意两个城市都能通车；全部修完仍不连通则输出 \(-1\)。 题面见 BISHI104 原题（牛客）。 题解见
solutions/BISHI104.py（已用官方样例验证）。
这题是「最小瓶颈生成树」的模板：答案就是 MST 中的最大边权。
理由：要让所有城市连通，必须选出一棵生成树； 完工时刻 = 这棵树里最晚修完的那条路； 要最小化「最大边」，就是最小瓶颈生成树 = MST（92.2 的推论一）。 而 Kruskal 按权升序加边，最后一次成功合并时的边权正是 MST 的最大边—— 所以根本不用跑完，第 \(N-1\) 次成功合并时就能立刻输出。
import sys
def main():
data = sys.stdin.buffer.read().split()
n, m = int(data[0]), int(data[1])
if n == 1: # ★ 只有一个城市，天然连通
sys.stdout.write("0\n")
return
edges = [None] * m
p = 2
for i in range(m):
x = int(data[p]); y = int(data[p + 1]); t = int(data[p + 2]); p += 3
edges[i] = (t, x, y) # t 放首位，直接 sort() 即按时间升序
edges.sort() # 按修完时刻从早到晚考虑每条公路
parent = list(range(n + 1)) # 并查集：维护「哪些城市已经互相通车」
size = [1] * (n + 1)
def find(x):
r = x
while parent[r] != r: # 一路向上找根
r = parent[r]
while parent[x] != r: # 迭代路径压缩，两趟写法
parent[x], x = r, parent[x]
return r
need = n - 1 # 连通 n 个城市恰好需要 n-1 次成功合并
for t, x, y in edges:
rx, ry = find(x), find(y)
if rx == ry:
continue # 这两城已通车，本条路不减少连通块数
if size[rx] < size[ry]:
rx, ry = ry, rx
parent[ry] = rx
size[rx] += size[ry]
need -= 1 # 只对「成功合并」计数，重边不会误计
if need == 0: # 第 n-1 次成功合并 = 全图连通
sys.stdout.write("%d\n" % t) # 当前这条边的时间就是答案
return # 它正是 MST 的最大边（最小瓶颈）
sys.stdout.write("-1\n") # 所有边用完仍没连通
main()
复杂度 \(O(M \log M)\)，瓶颈是排序。\(M = 10^5\) 轻松。
三个坑：
- \(N = 1\) 时答案是 0（一个城市天然连通，不需要任何公路）。
不特判的话
need初始就是 0，循环里永远触发不了need == 0， 会错误输出 \(-1\)。「规模为 1」的退化情况是模板题最常见的隐藏用例； - 计数用「成功合并的次数」而不是「扫过的边数」——重边和自环会让后者失真；
- 排序按 \(t\) 升序。写成
sort(key=lambda e: e[0])也对， 但把 \(t\) 放元组第一维直接sort()更快（省掉 \(10^5\) 次 lambda 调用）。
和二分答案的关系：这题也能「二分时间 \(T\) + 只用 \(t \le T\) 的边跑并查集验证连通」， 复杂度 \(O(M \log M \cdot \alpha)\)。但没必要——Kruskal 一遍扫过去就够了。 不过这个「二分 + 验证」的思路在瓶颈值不是边权（比如是某个函数）时是唯一出路， 见 44-二分。
这题也是并查集章的例题（38-并查集）。 两章的视角不同：38 章讲的是「并查集怎么用」，本章讲的是 「为什么答案等于 MST 的最大边」。同一份代码，两层理解。
92.9 本章速查¶
| 要点 | 结论 |
|---|---|
| MST 定义 | 无向连通图上权和最小的 \(n-1\) 条边 |
| 不连通 | 没有生成树，按题意输出 NO / \(-1\) |
| 边权可为负 | 贪心照样正确，别跳过负边 |
| 切割性质 | 任意切割的最小横跨边一定在 MST 里 → Prim |
| 环性质 | 任意环上的最大边一定不在 MST 里 → Kruskal |
| 推论 1 | MST = 最小瓶颈生成树（最大边最小） |
| 推论 2 | 所有 MST 的边权多重集相同 |
| 推论 3 | 边权互不相同 ⟹ MST 唯一 |
| Python 默认选 Kruskal | 排序在 C 层，只要边表，并查集常数极小 |
| Prim 的场景 | \(n \le 1500\) 的稠密图 / 完全图（邻接矩阵） |
| Kruskal 排序 | 把 \(w\) 放元组第一位 sort()，别用 key=lambda |
并查集 find |
必须迭代路径压缩 + 按大小合并 |
| 提前结束 | 选够 \(n-1\) 条就 break |
| \(n = 1\) | 答案 0 且视为连通——必查的退化情况 |
| 次小生成树 | MST + 枚举非树边 + 倍增求路径最大/次大边 |
| 严格 vs 非严格次小 | 严格的要维护「严格小于最大值」的次大边 |
| 规模 | Python 现实性 |
|---|---|
| Kruskal，\(m \le 3\times10^5\) | ✅ 排序 ~1 秒 + 并查集 ~2 秒 |
| Kruskal，\(m \le 10^6\) | ⚠️ 排序还行，并查集主循环 \(10^7\) 次，危险 |
| 朴素 Prim，\(n \le 1000\) | ✅ \(10^6\) 次迭代 |
| 朴素 Prim，\(n \le 2000\) | ⚠️ \(4\times10^6\) 次，勉强 |
| 堆优化 Prim，\(m \le 2\times10^5\) | ⚠️ 比 Kruskal 慢，除非题目只给邻接表 |
| 次小生成树（倍增），\(n \le 2\times10^4\) | ⚠️ 倍增表 \(18n\) 项已是上限 |
| 次小生成树，\(n \ge 10^5\) | ❌ 建表就超时 |
| 看到什么 → 想到 MST |
|---|
| 「用最小代价把所有点连起来」 |
| 「最早何时全部连通」→ Kruskal 取最大边（BISHI104） |
| 「任意两点路径的最大边最小」→ 最小瓶颈路 = MST 上的路径 |
| 「必须修某几条路」→ 先合并这些边再跑 Kruskal |
| 「代价是坐标距离」→ 完全图 → 朴素 Prim |