📚 覆盖：第 21–27 讲 · 重点：题 3、8、11、13、17 是本单元的核心证明。

第一部分：遍历（第 21–22 讲）

题 1（5 分）

(a) 握手引理是什么？它为什么保证"遍历所有顶点的所有邻居"是 Θ(V+E)？ (b) 邻接表与邻接矩阵在六个操作上各是什么复杂度？ (c) Facebook 有 30 亿用户、平均 200 个好友，用矩阵存需要多少空间？说明为什么必须用邻接表。 (d) 为什么复杂度必须写 O(V+E) 而不能只写 O(E)？

题 2（4 分）

(a) BFS 为什么必须在入队时标记已访问？出队时标记会怎样？ (b) 陈述并证明 BFS 求出的 dist 就是最短距离（分上界和下界）。 (c) BFS 求最短路的前提是什么？边权不同时该用什么？两者的关系是什么？

题 3（6 分）⭐

(a) 陈述括号定理，给出"v 是 u 的后代"的时间戳判据。 (b) 有向图 DFS 的四类边如何判定？哪一类等价于有环？ (c) 为什么环检测必须用三色？给出二色会误判的具体例子。 (d) 无向图环检测为什么要排除父边？

题 4（5 分）

(a) 证明"按完成时间降序排列即为拓扑序"，分三种颜色情形讨论。 (b) Kahn 算法如何检测环？如何改造它以得到字典序最小的拓扑序？ (c) Kahn 算法与并行任务调度有什么关系？

题 5（6 分）

(a) 证明凝聚图一定是 DAG。这个性质有什么用？ (b) Kosaraju 为什么第二遍要在反图上做？用"凝聚 DAG 的源"解释。 (c) Tarjan 中 low[u] = min(low[u], disc[v]) 为什么不能写成 low[v]？ (d) low[u] == disc[u] 为什么标志着 SCC 的根？

第二部分：并查集与 MST（第 23–24 讲）

题 6（5 分）

(a) 并查集不支持哪三类操作？这些限制换来了什么？ (b) 证明：只用按秩合并时，树高是 O(log n)。 (c) 为什么两个优化必须一起用？各自单独用能达到什么界？ (d) α(n) 在实际中是多少？为什么说"实质是常数"但严格说不是 O(1)？

题 7（4 分）

(a) 为什么可撤销并查集必须放弃路径压缩？复杂度变成多少？ (b) 并查集能处理"加边后询问连通性"，为什么处理不了"删边"？ (c) 给定一批 a==b 和 a!=b 的约束，如何用并查集判断是否矛盾？

题 8（7 分）⭐

(a) 陈述割性质，给出完整的交换论证证明。 (b) 环性质说了什么？它与割性质是什么关系？ (c) 通用 MST 算法的框架是什么？Kruskal 与 Prim 各选了哪个割？ (d) 证明：边权互不相同时 MST 唯一。边权有重复时什么仍然唯一？

题 9（5 分）

(a) 若边权都是 1 到 100 的整数，Kruskal 能做到多快？为什么？ (b) 为什么稠密图上数组版 Prim（O(V²)）优于堆版（O(E log V)）？ (c) 给出一个具体的图，说明 MST 上两点的路径不是最短路。 (d) 什么是最小瓶颈路？为什么 MST 上的路径就是它？

第三部分：最短路（第 25–26 讲）

题 10（4 分）

(a) 松弛操作的语义是什么？为什么说所有最短路算法只是"松弛顺序不同"？ (b) 填表：BFS / 0-1 BFS / DAG 松弛 / Dijkstra / Bellman-Ford 各自的松弛顺序与适用条件。

题 11（7 分）⭐

(a) 完整证明 Dijkstra 的正确性，明确指出"边权非负"用在哪一步。 (b) 给出一个具体的带负权图，说明 Dijkstra 会给出错误答案。 (c) 为什么"给所有边权加常数变成非负"是错的？举例。 (d) 惰性删除的写法为什么不改变复杂度？

题 12（6 分）

(a) 证明 Bellman-Ford 的循环不变式：“第 i 轮后 dist[v] ≤ 最多经过 i 条边的最短路”。 (b) 为什么 V−1 轮就够？第 V 轮还能松弛意味着什么？ (c) 如何找出负环上的具体顶点？ (d) SPFA 什么时候该用、什么时候不该用？

题 13（6 分）⭐

(a) 写出 Floyd-Warshall 的 DP 状态定义与递推式，说明"中间顶点"这个限定为什么关键。 (b) 为什么 k 必须是最外层循环？放在最内层语义变成什么？ (c) 为什么可以去掉第一维就地更新？ (d) 把 (min,+) 换成 (max,min) 得到什么问题的解？

题 14（6 分）

(a) 证明重赋权 ŵ(u,v) = w(u,v) + h(u) − h(v) 不改变最短路径的选择。 (b) Johnson 中 h(v) 取什么？为什么这样取能保证 ŵ ≥ 0？ (c) 为什么要引入连向所有顶点的虚拟源点，而不是随便选一个已有顶点？ (d) 稀疏图上 Johnson 与 Floyd-Warshall 的复杂度各是多少？

第四部分：网络流（第 27 讲）

题 15（5 分）

(a) 残量网络中反向边的作用是什么？ (b) 给出一个"没有反向边就得不到最优解"的具体例子并追踪。 (c) 成对存边（Rev 下标）的技巧为什么方便？

题 16（7 分）⭐

(a) 陈述最大流最小割定理的三个等价命题。 (b) 完成 (2 ⟹ 3) 的证明。 (c) 跑完最大流后如何在 O(V+E) 内找出最小割的边集？ (d) 为什么朴素 Ford-Fulkerson 的 O(E·|f*|) 不算多项式？构造一个需要百万次增广的图。 (e) Edmonds-Karp 只把 DFS 换成 BFS，为什么复杂度就变成多项式了？

题 17（6 分）⭐

(a) 把二分图最大匹配归约成最大流，说明容量设为 1 保证了什么。 (b) 陈述 König 定理，写出最大独立集与最大匹配的关系。 (c) 为什么这个关系只对二分图成立？一般图上这两个问题是什么难度？ (d) Dinic 在单位容量图上为什么是 O(E√V)？

题 18（5 分）

(a) 什么是"拆点"技巧？它解决什么建模需求？ (b) 什么样的问题适合建模成最小割？给一个例子并说明建图。 (c) 多源多汇怎么处理？

参考解答

题 1

(a) Σ deg(v) = 2E。因此"对每个顶点遍历其所有邻居"的总操作数是 Σ deg(v) = 2E = Θ(E)，而不是 V × max_deg = Θ(V·E)。

(b) 见第 21 讲的表：邻接表在空间 Θ(V+E)、遍历邻居 Θ(deg)、遍历所有边 Θ(V+E) 上占优；邻接矩阵在"判断某条边是否存在"Θ(1)、“删边"Θ(1) 上占优。

(c) 矩阵需要 (3×10⁹)² = 9×10¹⁸ 个位，即使 1 bit/边也是 10¹⁸ 字节 ≈ 10⁶ TB，完全不可行。邻接表只需 E = 3×10⁹×200/2 = 3×10¹¹ 条边的存储。真实世界的图几乎全是稀疏的。

(d) 稀疏图 E = Θ(V)，稠密图 E = Θ(V²)。省略任一项都会在某一类图上给出错误的复杂度。

题 2

(a) 出队时标记会导致同一顶点被多次入队（每条指向它的边都会入队一次），队列规模膨胀到 O(E)，且距离可能被错误覆盖。入队时标记保证每个顶点恰好入队一次。

(b)

上界 dist[v] ≥ δ(s,v)：dist 是沿某条实际路径累加的，不可能小于最短路。
下界 dist[v] ≤ δ(s,v)：对 δ 归纳。设 δ(s,v)=k，取最短路 s→…→u→v，δ(s,u)=k−1。由归纳假设 dist[u]=k−1；u 出队时会检查 v，此时若 v 未发现则赋值 k，若已发现则由队列的距离单调性 dist[v] ≤ k。∎

(c) 前提是所有边权相等。边权不同时用 Dijkstra——它本质就是"把 BFS 的队列换成优先队列”。

题 3

(a) 任意两顶点的 [disc, fin] 区间要么不相交、要么一个包含另一个，绝不部分重叠。判据：v 是 u 的后代 ⟺ disc[u] < disc[v] < fin[v] < fin[u]。

(b) 发现边 (u,v) 时看 v 的颜色：白 → 树边；灰 → 后向边（⟺ 有环）；黑且 disc[u]<disc[v] → 前向边；黑且 disc[u]>disc[v] → 横叉边。

(c) 二色（访问/未访问）会把前向边和横叉边误判为环。例：

a → b, a → c, b → c

DFS 从 a：访问 b，访问 c（完成），回到 a，再看 a→c——c 已访问
二色 ⟹ 误判为有环 ✗    实际上这是 DAG
三色 ⟹ c 是黑色（不在递归栈上）⟹ 横叉边，不是环 ✓

灰色的含义是"在当前递归栈上"，只有指向递归栈上的顶点才是环。

(d) 无向图中边 (u,v) 会同时出现在 u 和 v 的邻接表里。从 u 走到 v 后，v 的邻接表里有 u（已访问），若不排除会把这条同一条边误判为环。

题 4

(a) 设 (u,v) 是一条边，DFS 访问 u 时看 v：

v 白 ⟹ v 成为 u 的后代 ⟹ fin[v] < fin[u] ✓
v 黑 ⟹ v 已完成 ⟹ fin[v] < fin[u] ✓
v 灰 ⟹ 后向边 ⟹ 有环，与 DAG 矛盾

三种情形都有 fin[v] < fin[u]，故 fin 降序即拓扑序。∎

(b) 若输出的顶点数 < V，说明有顶点入度永远不为 0 ⟹ 存在环。字典序最小：把队列换成最小堆（每次取编号最小的入度 0 顶点）。

(c) 入度为 0 的顶点集合就是"当前可以并行执行的任务集合"。Kahn 算法本身就是一个并行任务调度器的骨架。

题 5

(a) 若凝聚图有环，环上所有 SCC 中的顶点互相可达，应属于同一个 SCC，与"极大"矛盾。∎ 用途：把任意有向图的分析化归为"SCC 内部" + “DAG 上的处理”（2-SAT、依赖循环检测、循环优化都靠它）。

(b) 第一遍 DFS 的完成时间逆序是凝聚 DAG 的拓扑序，所以最先处理的 SCC 是凝聚 DAG 的源。在反图上，源变成了汇——从它出发只能到达它自己内部的顶点（因为反图中它的所有出边都指向已处理完的 SCC）。于是每次 DFS 恰好困在一个 SCC 内。

(c) 因为 low[v] 可能已经被 v 从另一个方向的后向边压低到别的 SCC 的 disc 值上，用它会把不同 SCC 错误合并。后向边只能贡献 disc[v]（v 本身的发现时间）。⚠️ 在求割点/桥的变体中用 low[v] 才是对的，两个算法形似导致这个错误极常见。

(d) low[u] 是"u 的子树通过至多一条后向边能到达的最小 disc"。low[u] == disc[u] 说明 u 的子树无法逃出到更早的顶点 ⟹ u 是这个 SCC 在 DFS 树中的根，栈中 u 之上的顶点构成一个 SCC。

题 6

(a) 不支持：分裂（split）、删除元素、枚举某集合的所有成员（除非额外维护）。它只回答"是否在一起"——正是这种极度受限让它能做到近乎 O(1)。

(b) 秩为 k 的树至少有 2^k 个节点（对 k 归纳：秩 k 的树由两棵秩 k−1 的树合并而来，节点数 ≥ 2·2^{k−1}）。故 n ≥ 2^k ⟹ k ≤ log₂ n。∎

(c) 只按秩合并：树高 O(log n)，但每次 Find 都要重走整条路径。只路径压缩：摊还 O(log n)。两者结合：按秩合并保证树本来就矮，路径压缩把走过的路径拍平，每条路径最多被完整走一次 ⟹ O(α(n))。

(d) α(n) ≤ 4 对所有 n < 2^2^2^2^16（远超宇宙原子数 10⁸⁰）。但已证明 Ω(α(n)) 是 cell-probe 模型下的下界（Fredman & Saks 1989），不存在真正 O(1) 的并查集。

题 7

(a) 路径压缩改动了大量指针，无法回滚。放弃它后每操作 O(log n)（只靠按秩/按大小合并）。

(b) 并查集是"只增不减“的结构——合并后无法知道"如果去掉这条边会怎样”。删边需要 Link-Cut Tree 或 Euler Tour Tree（O(log²n)）；离线时可以用"时间分治 + 可撤销并查集"。⭐ 实用技巧：遇到"删边后询问连通性"，先想能不能离线倒过来处理，把删边变成加边。

(c) 先处理所有 a==b：Union(a,b)。再遍历所有 a!=b：若 Find(a)==Find(b) 则矛盾。⚠️ 顺序不能反。

题 8

(a) 割性质：对任意割，其最小横跨边属于某棵 MST。证明：设 e 是最小横跨边，某 MST T 不含 e。把 e 加入 T 形成环 C，C 必含另一条横跨边 e′（从 S 出去必须回来）。由 e 的最小性 w(e) ≤ w(e′)。令 T′ = T − e′ + e，仍是生成树且 w(T′) ≤ w(T)，故 T′ 也是 MST 且含 e。∎

(b) 环性质：任意环上权值最大的边（若唯一）不属于任何 MST。它与割性质是对偶的——割性质说"什么必须要"，环性质说"什么必须不要"。

(c) 框架：维护安全边集 A，重复 V−1 次找一条对 A 安全的边加入。Prim 选的割是"(已加入的顶点集, 其余)"——割固定、逐步长大；Kruskal 选的是"(当前最小边的 u 所在连通块, 其余)"——每次的割不同。

(d) 设有两棵不同 MST：T₁、T₂。取 T₁ △ T₂ 中权值最小的边 e，不妨 e ∈ T₁\T₂。把 e 加入 T₂ 形成环 C，C 中必有边 e′ ∉ T₁。由 e 的选取 w(e) < w(e′)，故 T₂ − e′ + e 更小，矛盾。∎ 边权有重复时 MST 的总权值仍唯一。

题 9

(a) 边权是小整数 ⟹ 可用计数/基数排序（第 12 讲）在 Θ(E + 100) 内排序。总复杂度降到 O(E α(V))，几乎线性。

(b) 稠密图 E = Θ(V²)：堆版是 O(V² log V)，数组版是 O(V²)。数组版少一个 log 因子。 因为稠密图上"找最小"的次数（V 次）远少于"更新 key"的次数（E 次），而堆让每次更新变贵了。

(c)

      A
   2 ╱ ╲ 2
    B───C
      3
MST = {A-B, A-C}（权 4）。B 到 C 在 MST 上要走 2+2=4，而直连边只要 3。

(d) 最小瓶颈路：使路径上最大边权最小的路径。MST 上的路径就是它——因为 MST 中任意两点的路径上的最大边，正是"连通这两点所必需的最小的最大边权"（由环性质：任何其他路径上必有一条边不小于它）。应用：找一条网络路径，使最脆弱的链路尽可能强。

题 10

(a) “如果经过 u 到 v 更近就更新”。dist[v] 始终是最短路的上界，单调下降直到收敛到 δ。所有最短路算法的差别只在于按什么顺序松弛哪些边。

(b)

算法	松弛顺序	条件	复杂度
BFS	按层	边权全相等	Θ(V+E)
0-1 BFS	双端队列（权 0 入队首）	边权 ∈{0,1}	Θ(V+E)
DAG 松弛	拓扑序	DAG，可负权	Θ(V+E)
Dijkstra	按 dist 递增	非负权	O(E log V)
Bellman-Ford	所有边 V−1 轮	任意权，可测负环	O(V·E)

题 11

(a) 反证。设 u 是第一个被取出时 dist[u] > δ(s,u) 的顶点。取一条 s→u 的最短路 P，设 P 上第一个不在 S 中的顶点是 y，前驱 x ∈ S。

x ∈ S 且 u 是第一个出错的 ⟹ dist[x] = δ(s,x)
x 取出时松弛了 (x,y) ⟹ dist[y] = δ(s,y)
由于边权非负 ⟹ δ(s,y) ≤ δ(s,u) ← 唯一用到前提的地方
u 被优先取出 ⟹ dist[u] ≤ dist[y] = δ(s,y) ≤ δ(s,u)，与假设矛盾。∎

(b)

          A
      1 ↙   ↘ 2
       B      C
        ↑    ↙
        └───┘  C → B 权 −2

真实最短路：A → C → B = 2 + (−2) = 0

Dijkstra 从 A 出发：
  ① 弹出 A（0）：松弛得 dist[B] = 1，dist[C] = 2
  ② 弹出 B（1 < 2）—— ⚠️ 此刻 Dijkstra 宣告 dist[B] = 1「已确定」
  ③ 弹出 C（2）：松弛 C→B 得 2 + (−2) = 0 < 1
     但 B 已出队并被视为确定，这次更新到不了它
  ⟹ 输出 dist[B] = 1，而正确答案是 0        ✗

⭐ 注意反例的构造要点：负边必须出现在一个已被「确定」的顶点之后。仅仅存在负边还不够——若负边恰好在顶点被确定之前就被松弛到，Dijkstra 仍会碰巧给出正确答案。这也是这类 bug 在实践中难以察觉的原因：带负权的图上 Dijkstra 常常「看起来是对的」。

(c) 加常数会偏向边数少的路径——一条 3 条边的路径被加了 3c，一条 1 条边的被加了 c，相对大小关系改变，最优解可能变。例：路径 A（3 条边，总权 1）vs 路径 B（1 条边，权 2）；加 c=5 后变成 16 vs 7，最优解翻转。

(d) 惰性删除让堆中最多有 O(E) 个条目，O(E log E) = O(E log V²) = O(2E log V) = O(E log V)——与标准版同阶。

题 12

(a) 对 i 归纳。i=0 时 dist[s]=0 ✓。设第 i−1 轮后成立，任取一条 s→v 的、边数 ≤ i 的最短路 s→…→u→v（s→u 段边数 ≤ i−1）。由归纳假设第 i−1 轮后 dist[u] 已正确，第 i 轮松弛 (u,v) 得到正确的 dist[v]。∎

(b) 无负环时最短路至多 V−1 条边（含环的话，非负环可去掉而路径不变长）。第 V 轮还能松弛 ⟹ 存在一条边数 ≥ V 的"更短"路径 ⟹ 必含负环。

(c) 记录第 V 轮被松弛的顶点 v，从它沿 parent 数组回溯 V 次——必然落入环内；再从该点沿 parent 走一圈即得整个负环。

(d) 有负权时用（它是 Bellman-Ford 的队列优化，平均常常接近 O(E)）；没有负权时永远用 Dijkstra。SPFA 最坏仍是 O(V·E)，且存在专门构造的反例图（网格图 + 特殊权值）使它退化。

题 13

(a) d[k][i][j] = i 到 j 的最短路，中间顶点只允许来自 {1..k}。递推：

d[k][i][j] = min(d[k−1][i][j], d[k−1][i][k] + d[k−1][k][j])

“中间顶点"这个限定是关键：起点终点不受限，只限制经过哪些中间点，这才使得"经过 k"的路径能拆成两段都不经过 k 的子路径（简单路径不重复顶点）。

(b) k 是 DP 的阶段，i、j 是状态。DP 必须按阶段推进——所有 (i,j) 对必须在同一个"允许集合"下同步演进。k 放内层会在 d[i][k] 和 d[k][j] 还没算好时就使用它们，结果错误（且错得隐蔽——很多图上仍碰巧正确）。

(c) 因为 d[k][i][k] = d[k−1][i][k]（从 i 到 k 的最短路不会把 k 用作中间点），同理 d[k][k][j] = d[k−1][k][j]。所以就地更新时读到的第 k 行第 k 列仍是上一层的值。

(d) ⚠️ 注意别答反。松弛式是 d[i][j] = OP₁(d[i][j], OP₂(d[i][k], d[k][j]))：

(OP₁, OP₂)	含义	问题
`(min, +)`	路径边权之和最小	最短路
`(max, min)`	路径上最小边权的最大值	⭐ 最大瓶颈路（widest path，最大带宽路径）
`(min, max)`	路径上最大边权的最小值	最小瓶颈路（就是 MST 上的路径，见题 9(d)）
`(or, and)`	是否可达	传递闭包
`(+, ×)`	路径条数	计数

所以 (max, min) 给出的是最大瓶颈路：在网络中找一条 u→v 的路径，使这条路径的带宽瓶颈尽可能大。

⭐ 只要 (OP₁, OP₂) 构成一个半环（OP₂ 对 OP₁ 满足结合律与分配律），Floyd-Warshall 的三重循环框架就原样成立——这是把具体算法抽象成代数结构的漂亮例子。

题 14

(a) 望远镜求和：

ŵ(v₀→…→vₖ) = Σ[w + h(vᵢ) − h(vᵢ₊₁)] = w(路径) + h(v₀) − h(vₖ)

中间的 h 全部消掉。同样两点之间，所有路径的权值都改变了相同的量，最短路径的身份不变。∎

(b) h(v) = δ(q, v)（从虚拟源点 q 到 v 的最短距离）。由三角不等式 h(v) ≤ h(u) + w(u,v)，即 w(u,v) + h(u) − h(v) ≥ 0。✓

(c) 因为要求 h(v) 对所有顶点有定义且有限。随便选一个已有顶点可能到不了某些顶点（h = ∞），重赋权就无法进行。虚拟源点连向所有顶点（权 0）保证了全部可达。

(d) 稀疏图 E = Θ(V)：Johnson O(V·E log V) = O(V² log V)；Floyd-Warshall Θ(V³)。Johnson 明显更优。

题 15

(a) 允许算法**“后悔”**——如果之前的流路由不好，后面的增广路可以通过反向边把流退回来重新路由。没有它，贪心找到的第一条路可能永久堵死更优的方案。

(b)

s→a(1), s→b(1), a→b(1), a→t(1), b→t(1)

无反向边：先走 s→a→b→t（流 1），此后 s→b 被 b→t 堵死 ⟹ 最大流 = 1 ✗
有反向边：第二条增广路 s→b→(a←b 反向)→a→t ⟹ 总流 2 ✓（这就是最优）

(c) 正反两条边相邻存放，推流时 e.Cap -= d 同时 adj[e.To][e.Rev].Cap += d，两行搞定，不需要额外的边查找。

题 16

(a) ① f 是最大流；② 残量网络中无增广路；③ 存在割 (S,T) 使 |f| = c(S,T)。三者等价，故最大流值 = 最小割容量。

(b) 设 S = 残量网络中从 s 可达的顶点集，T = V−S。因无增广路，t ∉ S，(S,T) 是合法割。对任意 u∈S、v∈T：

边 (u,v) 必满流（否则残量 > 0，v 就可达）
边 (v,u) 必零流（否则反向残量 > 0，v 也可达）

故 |f| = c(S,T)。∎

(c) 在残量网络上从 s 做一次 BFS/DFS，可达的顶点集就是 S，从 S 指向 T 的原图边就是最小割的边集。Θ(V+E)。

(d) 因为 |f*| 是数值，其编码长度是 log|f*|，所以 O(E·|f*|) 关于输入长度是指数的（伪多项式，参见第 31 讲）。构造：

s→a(10⁶), s→b(10⁶), a→b(1), a→t(10⁶), b→t(10⁶)
每次增广路都走中间那条容量 1 的边 ⟹ 需要 2×10⁶ 次增广

(e) BFS 保证每次找的是边数最少的增广路。可以证明：每次增广后，某条边的"关键边"距离严格增加，每条边最多成为关键边 O(V) 次，故增广次数是 O(V·E)——与容量完全无关。这就把复杂度从伪多项式变成了 O(V·E²)。

题 17

(a) 建图：s→每个左顶点（容量 1）、原图每条边（容量 1 或 ∞）、每个右顶点→t（容量 1）。容量 1 保证每个顶点最多被用一次——这正是匹配的定义。整数性定理保证最大流可取整数值，每条流量为 1 的路径对应一条匹配边。

(b) König 定理：二分图中 最大匹配数 = 最小顶点覆盖数。推论：最大独立集 = n − 最大匹配（因为独立集与顶点覆盖互补）。

(c) König 定理的证明依赖二分结构（用最大流最小割或增广路论证）。一般图上最大独立集和最小顶点覆盖都是 NP-完全的（第 34 讲）——⭐ 二分结构是让它们变简单的唯一原因。（一般图的最大匹配仍是多项式的，靠 Edmonds 的带花树算法。）

(d) 单位容量图上，每个阻塞流阶段后分层图的层数至少 +1，而流值不超过 O(√E)，可以证明阶段数是 O(√V)，每阶段 O(E)，故 O(E√V)。

题 18

(a) 把顶点 v 拆成 v_in → v_out 两个点，中间边容量 = 该顶点的容量限制。解决"顶点也有容量限制"这一建模需求（流网络原本只能给边设容量）。也用于"每个点只能经过一次”（容量设 1）。

(b) 形式为"每个元素必须二选一，某些组合产生代价“的问题。例：图像分割——每个像素归前景（S 侧）或背景（T 侧），像素本身的前景/背景倾向做成到 s/t 的边，相邻像素颜色差异做成它们之间的边（分开就要付这个代价）。最小割 = 最优分割。

(c) 加一个超级源 S 连向所有源点（容量为该源的供应量或 ∞），加一个超级汇 T 接收所有汇点的边，然后求 S→T 的最大流。

第一部分：遍历（第 21–22 讲）#

题 1（5 分）#

题 2（4 分）#

题 3（6 分）⭐#

题 4（5 分）#

题 5（6 分）#

第二部分：并查集与 MST（第 23–24 讲）#

题 6（5 分）#

题 7（4 分）#

题 8（7 分）⭐#

题 9（5 分）#

第三部分：最短路（第 25–26 讲）#

题 10（4 分）#

题 11（7 分）⭐#

题 12（6 分）#

题 13（6 分）⭐#

题 14（6 分）#

第四部分：网络流（第 27 讲）#

题 15（5 分）#

题 16（7 分）⭐#

题 17（6 分）⭐#

题 18（5 分）#

参考解答#

题 1#

题 2#

题 3#

题 4#

题 5#

题 6#

题 7#

题 8#

题 9#

题 10#

题 11#

题 12#

题 13#

题 14#

题 15#

题 16#

题 17#

题 18#

第一部分：遍历（第 21–22 讲）

题 1（5 分）

题 2（4 分）

题 3（6 分）⭐

题 4（5 分）

题 5（6 分）

第二部分：并查集与 MST（第 23–24 讲）

题 6（5 分）

题 7（4 分）

题 8（7 分）⭐

题 9（5 分）

第三部分：最短路（第 25–26 讲）

题 10（4 分）

题 11（7 分）⭐

题 12（6 分）

题 13（6 分）⭐

题 14（6 分）

第四部分：网络流（第 27 讲）

题 15（5 分）

题 16（7 分）⭐

题 17（6 分）⭐

题 18（5 分）

参考解答

题 1

题 2

题 3

题 4

题 5

题 6

题 7

题 8

题 9

题 10

题 11

题 12

题 13

题 14

题 15

题 16

题 17

题 18