图系列第 14 篇：网络流——最大流最小割

嘿，朋友，欢迎回到图系列。这是第 14 篇，也是整个图系列从”探索图”转向”利用图”的分水岭。前面十三篇，我们学会了怎么存图（第 3 篇的邻接矩阵与邻接表）、怎么把图走遍（第 4 篇的 BFS、第 5 篇的 DFS）、怎么给图排序（第 7 篇拓扑排序）、怎么在图上找最短路径（第 8 到 11 篇的 Dijkstra、Bellman-Ford、Floyd-Warshall），还学会了怎么用最少的边把图连起来（第 12 篇最小生成树）。从今天起，我们要问一个全新的问题：图不仅能用来”走”，还能用来”运输”。把图的边想象成管道，把顶点想象成中转站，那么从某个起点到某个终点，最多能同时输送多少”货物”？这就是网络流（Network Flow）研究的核心问题，而今天这篇要解决的，正是其中最经典、最优雅的一个：最大流问题（Maximum Flow）。

先打一个预防针：这一篇的内容密度会比较高，因为网络流不是一个孤立的小技巧，而是一整套”建模—算法—证明—应用”的思想体系。好消息是，它的每一步都有非常直观的物理图景可以依托——水、管道、阀门、水箱。只要你能想象水怎么流，你就能理解残量图、增广路径和最大流最小割定理。而且我们不会让任何概念悬在空中：每一节都会有 mermaid 配图，中间还会安排两场完整的”手算走查”，把每一轮增广的残量图都画出来。

在出发之前，先回顾一下第 4 篇的主角——BFS。当时我们用它解决了”无权图上从起点到终点最少走几步”的问题：从起点出发一圈一圈向外扩散，用一个队列维护访问顺序，用一个 visited 数组保证每个顶点只入队一次，当某个顶点第一次被访问时，我们走过的边数就是它到起点的最短距离。为什么今天又要请出 BFS？因为本篇的核心算法 Edmonds-Karp 正是”用 BFS 在残量网络上找增广路径”：残量网络是一张随流量变化而变化的图，BFS 负责在其中找到从源到汇的最短路径（边数最少），然后沿着这条路径”多送一批水”。你马上会看到，BFS 的层序扩散特性在这里发挥着惊人的作用：它保证增广次数是多项式级的，让朴素的 Ford-Fulkerson 思想蜕变成一个真正实用的算法。可以说，第 4 篇埋下的那颗种子，今天要长成一棵大树了。

本篇的路线图如下：第 1 节从配水管网的真实问题出发，建立容量、流量、守恒三个直觉概念；第 2 节把直觉翻译成严格的数学语言，给出流网络和可行流的定义；第 3 节引入整篇的灵魂——残量网络，以及那条神奇的”反向边”；第 4 节介绍增广路径，讲清楚”沿着残量路径多送水”为什么安全；第 5 节依次展开 Ford-Fulkerson 思想与 Edmonds-Karp 算法，并用两场完整手算把每一轮残量图画出来；第 6 节给出 JS/TS 的完整代码并逐行解释；第 7 节登上本篇的理论高峰——最大流最小割定理，并教你怎么从最后一次 BFS 直接读出最小割；第 8 节介绍最大流的经典应用，重点预告第 15 篇的二分图匹配；最后是速查表、自测题和下一篇预告。内容很多，但我们一步一步来。

1 问题：水管网络最多能送多少水

1.1 从一座供水站说起

想象你是一座城市供水工程的总设计师。城市西边有一座水源地 S（Source，源），东边有一个蓄水池 T（Sink，汇），两者之间铺设了一张复杂的配水管网。每根管子都有自己固定的粗细，也就是容量（Capacity）：单位时间内，这根管子最多能通过多少立方米的水。你的任务很朴素：在不撑爆任何一根管子的前提下，让从 S 流进、T 流出的水量尽可能大。这个”尽可能大”的数字，就叫最大流（Max Flow）。

为什么这个问题值得单独写一篇？因为”每根管子都有上限”这一点，让问题变得远比”两点之间找一条最粗的路”复杂。你当然可以找到 S 到 T 之间最粗的一条单一路径，但整张网可以同时使用几十条路径；而且路径之间还会互相争抢管段——两条不同的路线可能共用同一条中间管道，你在这条路线上多送 1 吨水，就可能挤占另一条路线的份额。更微妙的是，某些”看起来很好”的分配方案会把关键的中间管道占满，导致后面的水流全部被堵死，而一个聪明的调度员会主动撤掉之前一部分水的运输路线，给更优的全局方案让路。这三层复杂性，恰好对应了网络流理论的三个核心概念：容量约束、流量守恒、反向边反悔。

先看一张最小的配水管网，只有五个顶点和五条管道。S 是水源，T 是蓄水池，A 和 B 是两个中转加压站，数字标在管道旁边的是容量（单位：立方米/秒）：

graph LR
    S["S 水源"] -->|"10"| A["A 加压站"]
    S -->|"10"| B["B 加压站"]
    A -->|"8"| T["T 蓄水池"]
    B -->|"10"| T
    A -->|"2"| B

请先凭直觉猜一猜：这张网最多能送多少水？有人会回答”把 S 伸出去的两根管子加起来，10 + 10 = 20”；也有人会回答”把通向 T 的两根管子加起来，8 + 10 = 18”。正确答案恰恰是 18，但它是怎么来的呢？看看聪明的分配方案：S→A 走满 10，其中 8 直接到 T；剩下 2 吨水怎么办？A→T 已经满了，但 A 和 B 之间还有一根容量为 2 的管子，于是 A 把多出来的 2 吨转给 B，由 B 再送到 T。与此同时，S→B 走 8 吨就够了——因为 B→T 的 10 里已经有 2 吨被 A 转来的水占用，还剩 8。最终：S→A 走 10，S→B 走 8，总流量 10 + 8 = 18；A→T 走 8，A→B 走 2，B→T 走 10，T 收到 8 + 10 = 18。请花十秒钟核验守恒：A 流入 10，流出 8 + 2 = 10；B 流入 8（来自 S）+ 2（来自 A）= 10，流出 10（去 T）。每个中转站都”进多少出多少”，所有管子都没超载，所以 18 是一个合法的输送方案，而且它是这张网的最大流。

注意，18 这个答案既不是”S 出边之和 20”，也不是”T 入边之和 18”？等等，T 入边之和恰好也是 18，这是巧合还是必然？是必然：因为 S 流出的水最终都要到 T，且中间不损耗、不滞留，所以只要流量守恒成立，T 的总流入一定等于 S 的总流出。真正需要费心思的，是让”从 S 送出的水”和”T 能接收的水”在中间网络上恰好衔接起来。在这个例子里，A 的 2 吨剩余恰好能被 B 接住，B→T 的富余容量也恰好够用——这种”恰好”不是运气，而是流量守恒约束下的必然结果，也是第 2 节形式化的动力。

这个小例子已经把关键味道都带出来了：容量是管道的硬上限，守恒是中转站的记账规则，而”多出来往隔壁转”就是多路径协同。下面我们把这三个直觉逐一钉死。

1.2 三个直觉概念：容量、流量、守恒

容量（Capacity）。每根管道 u→v 上刻着一个非负数字 c(u, v)，表示单位时间内最多能通过的水量。容量是管子的物理属性，与水流实际有多少无关。在图中我们通常把它标在边上。有些边容量为 0，等价于不存在这条边。

流量（Flow）。我们真正派到每根管道上的水量记作 f(u, v)，它必须满足两条铁律。第一，非负且不超容：0 ≤ f(u, v) ≤ c(u, v)，水只能沿着箭头方向流，不能倒流，而且绝不能超过管径；第二，中转站守恒：对除源 S 和汇 T 之外的每个顶点，流入总量必须等于流出总量。为什么是 S 和 T 例外？因为 S 是水的来源，水从它”凭空产生”，T 是水的归宿，水到它那里”凭空消失”。除了这两个端点，任何一个中转站都不能凭空多出水，也不能偷偷存水——我们假设所有管道都是即时输送的稳态系统，管子里不存在越积越多的水。

于是，整张网络”总共送了多少水”就有了一个干净的定义：S 的净流出量（S 流出的总和减去 S 流入的总和），或者等价地，T 的净流入量。由于除了 S、T 之外每个顶点都守恒，这两个数字必然相等。这个总数值记为 |f|，叫流的值（Value of the Flow）。注意”流”这个字在中文里经常身兼两职：它既可以指整张网络上所有边流量组成的一个方案（一个流），也可以指某条边上的具体水量（一股流）。读文章时请根据语境区分。

配水管网的比喻到这里已经足够。但为了给后续的算法铺路，我们把”水”换成更一般的”货物”：边的容量是运输能力的上限，流量守恒是”中间仓库不留货”的规则，流的值就是从源头发出的货物总量。无论问题是电力调度、数据包路由、交通流分配还是任务指派，只要抽象成这个模型，下面的理论全部适用。

1.3 为什么不能简单”找最粗的路”

在正式开始之前，值得花一点时间消灭一个常见误区：最大流不等于”最粗路径上的容量”。

第一，多路径并行。即使单条路径的容量不大，多条路径叠起来也可以远超任何单一路径。上面那张图里，最粗的单一路径 S→A→T 只有 8，但整张网能送 18。

第二，路径互相干扰。如果两条路径共用一根管道，它们就会在这个管段上竞争容量。你送多了，我就得少送；这种竞争关系用朴素”找路径”的思路很难全局地处理。

第三，局部最优会堵死全局最优。请看下面这张网。S→A 和 S→B 都是 10，A→T 和 B→T 都是 10，中间还有一根细细的 A→B，容量只有 2。最粗的路径显然是 S→A→T 或 S→B→T，各走 10，总流 20，看起来一点问题都没有。但假如调度员一时糊涂，先让 2 吨水沿着 S→A→B→T 走了（这根细管道容量恰好是 2），之后会发生什么？

graph LR
    S["S"] -->|"10"| A["A"]
    S -->|"10"| B["B"]
    A -->|"2"| B
    A -->|"10"| T["T"]
    B -->|"10"| T

那 2 吨水占了 A→B 和 B→T 各 2 的容量。接下来 A→T 还能走 10（A→T 没被占），B→T 还剩 8，S→A 还剩 8，S→B 还剩 10。如果调度员将错就错，他可能会让 S→A→T 走 8、S→B→T 走 8，加起来 2 + 8 + 8 = 18——比最优的 20 少了 2！要想拿回这 2，唯一的办法是把”先送进 A→B 的那 2 吨水”撤回来：让 A 的这 2 吨改走 A→T，让 B 缺的 2 吨改由 S→B 直接供给。也就是说，我们需要一种机制，允许算法”撤销”之前做出的边上的分配。这就是第 3 节反向边登场的理由——它是整个网络流算法里最反直觉、也最精华的一笔。

1.4 动手体验

理论讲得再多，也不如亲手拖一拖图。下面的交互实验室里提供了图算法可视化环境，你可以把今天的配水管网图输入进去，也可以直接体验后面要讲的 BFS 找路过程。建议在学习残量网络和增广路径时反复回到这里，把每一步走查的结果亲手验证一遍：

好，直观问题已经建立。接下来我们把”管道、水、记账规则”翻译成严谨的数学语言。

1.5 常见问题快问快答

在进入形式化定义之前，先集中回答几个新手最爱问的问题，避免它们在中途打断思路。

问：为什么网络必须是有向图？无向管道怎么办？ 答：运输方向是网络流的核心信息，所以默认用有向图。容量为 c 的无向管道可以拆成两条有向边：u→v 容量 c 和 v→u 容量 c，各自独立参与流量分配。数学上允许两个方向同时有流量（比如 f(u,v) = 3、f(v,u) = 1），但可以证明一定存在一个最优解不会同时使用两个方向——把两个方向的流量互相抵消即可。所以放心拆，不会因此漏掉最优解。

问：流量必须守恒的顶点包括源和汇吗？ 答：不包括。只有中间顶点要求”进 = 出”；源是水的发源地、汇是水的归宿，两者的不平衡恰恰定义了流的值。

问：容量可以是负数吗？ 答：不可以。容量是承载上限，必须 c ≥ 0；流量也必须非负。如果问题里出现”亏损”之类的负收益，建模时通常把它放到”成本”而不是”容量”里。

问：如果图里有重边（多条 u→v）怎么办？ 答：把它们当成多条独立管道即可。残量图里每条边都有自己的正向和反向记录，BFS 会逐条检查；你也可以先把容量合并成一条边，结果相同，只是图更小。

问：最大流会等于无穷大吗？ 答：只要所有容量有限，最大流一定有限——它被任何割的容量（有限值）限制住。容量为 ∞ 的边只作为建模工具出现（比如超级源连向多个真实源），真正卡住流量的永远是那些有限容量的瓶颈。

问：为什么叫”源”和”汇”，而不是”起点”和”终点”？ 答：因为网络流里的 S 和 T 不只是”路径的端点”，而是整个系统水流的来源与归宿：S 只有净流出、T 只有净流入，中间顶点严格守恒。用”源/汇”能准确传达这种不对称的角色，也提醒你：不是每条路径都从 S 到 T 才算数，残量图里”绕行”和”撤回”同样是合法的移动。

2 流网络形式化：从直觉到定义

2.1 流网络的四件套

一个**流网络（Flow Network）**由四样东西组成：一张有向图、一个源、一个汇、一个容量函数。

有向图 G = (V, E)。V 是顶点集合，E 是有向边集合。每一条边 u→v 都表示”货物只能从 u 运到 v”的方向。为什么必须是有向的？因为现实中很多运输通道本来就是单向的：输油管里的油只能朝一个方向泵，单向车道只能朝一个方向开，网络数据包沿着链路的方向转发。即使现实中的管道是双向的（比如自来水管可以双向送水），我们也可以把它拆成两条方向相反的有向边，各自标上容量。

源 S 与汇 T。S 是唯一的”发货点”，T 是唯一的”收货点”，二者都是顶点，且 S ≠ T。定义并不强制 S 不能有入边；只是任何从外面流入 S 的水都不会帮助我们增加从 S 发出的总量，所以在讨论最大流时，我们总可以忽略它们。

容量函数 c。对每条边 e = (u, v)，给定一个非负实数 c(u, v) ≥ 0，表示边上的最大承载量。容量为 0 的边通常直接省略。为了让记号简洁，对于图中不存在的边，我们约定 c(u, v) = 0。在算法竞赛和大部分应用里，容量都是整数；整数容量有一个非常重要的好处——后面你会看到，每轮增广都能保证增加整数流量，从而保证算法在有限步内终止。这也是为什么 Edmonds-Karp 的复杂度分析建立在整数容量上。

于是流网络可以记为 (G, S, T, c)，或者更简单地写作”图 + 容量”。下面这张图就是一个标准的流网络：顶点 S 是源，顶点 T 是汇，每条边上标着容量。注意边的方向决定了水的走向：

graph LR
    S["S (源)"] -->|"c=10"| A["A"]
    S -->|"c=5"| B["B"]
    A -->|"c=8"| C["C"]
    B -->|"c=7"| C
    A -->|"c=3"| B
    C -->|"c=15"| T["T (汇)"]

这张图有一个特点值得注意：A 和 B 之间有一条 A→B 的边，方向是从 A 到 B，而 S 同时连向 A 和 B。也就是说，这张网络允许”A 把水转给 B”这样的绕行结构——它看起来像捷径，实际上可能改变最优分配的形态。我们在第 2.2 节会在这张图上构造一个可行流，请记住它的拓扑。

2.2 可行流的三个条件

有了网络，再定义流（Flow）。一个流是定义在所有顶点对上的函数 f：V × V → R，它必须同时满足三个条件：

容量约束（Capacity Constraint）：对任意边 (u, v) ∈ E，都有 0 ≤ f(u, v) ≤ c(u, v)。也就是说，每条边上的流量非负、不超过容量。对不在 E 中的顶点对，f(u, v) 一律视为 0，这样求和时就不必反复检查边是否存在。

流量守恒（Flow Conservation）：对任意顶点 u ∉ {S, T}，有 Σ_{v∈V} f(u, v) = Σ_{v∈V} f(v, u)。左边是 u 流向所有邻居的总量，右边是所有邻居流向 u 的总量；两者必须相等。这就是”中转站不积水”的数学形式：进来的等于出去的。

流的值（Value）：|f| = Σ_{v∈V} f(S, v) − Σ_{v∈V} f(v, S)。如果我们把注意力放在”从 S 净流出多少”，这个量就是整个流方案的”产量”。由于守恒条件，|f| 也恰好等于 T 的净流入 Σ_{v∈V} f(v, T) − Σ_{v∈V} f(T, v)。这个等式值得记一辈子：S 流出的水最终全部到达 T（中途没有损耗、没有滞留）。

满足以上所有条件的流叫可行流（Feasible Flow）。任何一张网络上至少存在一个可行流——零流：每条边的流量都取 0，容量约束成立，守恒平凡成立，流的值是 0。零流虽然毫无价值，但它给所有算法提供了一个”合法起点”。最大流问题就是：在所有可行流中，找出使 |f| 最大的那个。

下面这张图展示了一个具体的可行流，边上标注”流量/容量”。请逐点验证：每条边流量 ≤ 容量；A 流入 8（来自 S），流出 6 + 2 = 8；B 流入 5 + 2 = 7，流出 7；C 流入 6 + 7 = 13，流出 13；S 流出 8 + 5 = 13；T 流入 13。全部对上，这是一个合法的可行流，值 = 13：

graph LR
    S["S"] -->|"8/10"| A["A"]
    S -->|"5/5"| B["B"]
    A -->|"2/3"| B
    A -->|"6/8"| C["C"]
    B -->|"7/7"| C
    C -->|"13/15"| T["T"]

请花一分钟亲自核验这张图的守恒：A 进 8 出 6+2；B 进 5+2 出 7；C 进 6+7 出 13；S 出 8+5；T 入 13。全部对得上。这个流的值是 13，但它未必是最大流——事实上我们可以从”哪条边还没满”入手，试着再多塞一些。但问题来了：S→B 已经满了，S→A 还剩 2，A→C 还剩 2，B→C 也满了，C→T 还剩 2。直觉告诉我们好像还能加一点，但加在哪里、会不会破坏守恒？这正是残量网络要回答的问题。

2.3 几个容易混淆的记号与约定

第一，容量与流量的单位。容量 c 是”最大能力”，流量 f 是”实际分配”，两者同单位但含义不同。一张图上如果只标一个数字，通常指容量；如果标”a/b”，通常指流量 a、容量 b。本文采用”流量/容量”的写法，并在文字里明确说明。

第二，反向边怎么办。定义里我们要求 f(u, v) ≥ 0，即不允许”反向流量”。如果现实网络有一条反向管道 v→u 且容量为 c(v, u)，我们会把它作为一条独立的有向边加入图中，流量同样满足 0 ≤ f(v, u) ≤ c(v, u)。千万不要把”反向流量”和”反向边”混为一谈：前者是原问题中的真实管道，后者是第 3 节要讲的、算法虚拟出来的撤销机制。

第三，为什么守恒对 S、T 豁免。这不是偷懒，而是数学上必须的：如果 S 也要守恒，那么 S 的净流出必须为 0，流的值永远为 0，最大流问题就毫无意义。T 同理。正是这两个”漏洞”让水得以从源头进入网络、从汇口离开网络。

第四，多源多汇怎么办。现实中可能有多个水源和多个用水点。处理方式非常优雅：新建一个超级源 S*，用容量 +∞ 的边连向所有真实源；再新建一个超级汇 T*，用容量 +∞ 的边把所有真实汇连向它。这样就把多源多汇问题归约成了标准单源单汇问题。这个”加超点”的技巧会在第 8 节反复出现，请先记在脑子里。

2.4 从可行流到最大流：问题已经精确

现在我们可以把第 1 节的故事用一句话重述：在满足容量约束与流量守恒的所有可行流中，最大化 S 的净流出量。这是一个典型的线性规划问题（变量是每条边的 f(u,v)，约束全是线性的），但网络流之所以被单独研究，是因为它的结构允许我们用组合算法高效求解，而不必调用通用线性规划工具。

那么，怎么找最大流？朴素想法是”不断多塞一些水进去，直到塞不动为止”。这个朴素想法离正确答案只有一步之遥，而缺失的那一步，正是残量网络与增广路径。下一节，我们迈出这一步。

2.5 双向管道与反平行边：建模细节

第 2.3 节约定过”不允许反向流量”，但现实问题里经常出现真正的双向管道。这里把建模细节说透，因为它在代码里非常容易踩坑。

无向边的拆分。 无向边 {u, v} 容量 c 拆成 u→v 容量 c 和 v→u 容量 c 两条有向边。在代码里调用两次 addEdge 即可。注意：网络流算法会为每条 addEdge 自动创建一条残量反向边（初始残量 0），所以两条真实有向边 + 两条残量反向边一共产生四条邻接表记录。它们互不干扰：u→v 的真实边对应残量反向边 v→u（初始 0），v→u 的真实边对应残量反向边 u→v（初始 0）。BFS 在残量图里看到四条边，其中两条是”还能加”、两条是”还能撤”，行为完全正确。

反平行边的另一种形态。 如果原问题里 u→v 和 v→u 的容量不同（比如 c1 = 5、c2 = 3），同样各自 addEdge，算法会分别处理。由于残量反向边可能与另一条真实边”方向重合”，初学者常误以为它们会互相覆盖——不会，它们在邻接表里是不同的对象，cap 各自维护。

同时双向流动需要担心吗？ 假设拆完无向边后，某时刻 f(u,v) = 4、f(v,u) = 1。物理上这相当于净送 3 单位从 u 到 v，还白占了 1 单位两边的容量。虽然数学上合法，但可以证明最大流一定存在一个”不同时双向”的最优解（把较小的那个方向的流量减掉即可），所以算法找到的解不会出现这种浪费。知道这一点，你就不会被”两个方向都有流”的中间状态吓到。

重边合并。 多条同向边可以合并成一条容量之和的边，也可以保留多条。合并后图更小、BFS 更快；保留多条则路径选择更接近原始网络。两者给出的最大流相同。

3 残量网络：给”反悔”留一条路

3.1 什么叫”还能再塞多少”

假设我们已经有了一个可行流，比如 2.2 节那张图。现在想知道：还能不能再提高总流量？答案不能只看”还有哪条边没满”。因为即使每条从 S 出发的路径上都至少有一根管子满了，我们仍有可能通过重新分配来增加流量——这正是 1.3 节里那 2 吨水的教训。

为了系统地回答”还能再塞多少”，网络流理论发明了一个关键工具：残量网络（Residual Network），也叫剩余网络。它是在当前流的基础上派生出来的一张新图，顶点集和原图相同，边则由两部分组成：

正向剩余边。对每条原边 u→v，如果当前流量 f(u, v) 小于容量 c(u, v)，就保留一条从 u 到 v 的边，容量（残量）为 c(u, v) − f(u, v)，含义是”这根管子上还能再正向多送多少水”。

反向剩余边。对每条原边 u→v，只要当前流量 f(u, v) > 0，就添加一条从 v 到 u 的边，容量（残量）为 f(u, v)，含义是”我可以从 v 往 u 撤回多少水”。

残量网络记作 G_f。它的每条边都带着一个正残量；残量为 0 的边不画出来。特别注意：残量网络的边不一定是原图的边——反向边就是原图里不存在（或方向相反）的边，它们是算法虚拟出来的”后悔药”。

下面左边是 2.2 节的当前流（流量/容量标注），右边是它对应的残量网络。先看正向部分：S→A 已用 8 剩 2，所以残量图里有 S→A 容量 2；A→C 已用 6 剩 2；C→T 已用 13 剩 2。再看反向部分：S→A 有 8 的流量，所以残量图里有 A→S 容量 8；A→B 有 2 的流量，所以残量图里有 B→A 容量 2；其余同理：

graph LR
    subgraph L["当前流 f"]
        S1["S"] -->|"8/10"| A1["A"]
        S1 -->|"5/5"| B1["B"]
        A1 -->|"2/3"| B1
        A1 -->|"6/8"| C1["C"]
        B1 -->|"7/7"| C1
        C1 -->|"13/15"| T1["T"]
    end
    subgraph R["残量网络 G_f"]
        S2["S"] -->|"2"| A2["A"]
        A2 -->|"2"| C2["C"]
        C2 -->|"2"| T2["T"]
        A2 -->|"8"| S2
        B2["B"] -->|"5"| S2
        B2 -->|"2"| A2
        A2 -->|"1"| B2
        C2 -->|"6"| A2
        C2 -->|"7"| B2
        T2 -->|"13"| C2
    end

注意残量图里的细节：S→B 已满（5/5），正向残量是 0，不画；但它有反向边 B→S 容量 5。A→C 已用 6，剩 2，所以有正向 A→C 2 和反向 C→A 6。B→C 已满，只有反向 C→B 7。C→T 已用 13，剩 2，有正向 C→T 2 和反向 T→C 13。整张残量图把”当前状态下所有还能改变流量的动作”都列了出来：往前走是增加，往回走是撤回。

请对照左右两半，逐个检查每一条残量边是从哪里来的：正向残量 = 容量 − 流量，反向残量 = 流量。这个过程一开始有点机械，但一旦熟练，你就能在脑子里把任意一张”流量/容量”图直接翻译成残量图——这是手算和调试代码的基本功。

3.2 反向边的含义：不是真的倒流

很多初学者在这里卡住：反向边是不是意味着水真的会倒流？会不会违反”0 ≤ f ≤ c”和守恒？

答案是：反向边只是记账工具，不是真实的物理管道。算法的真实状态永远是原图边上的流量 f(u, v)（始终非负、不超容）。反向边的残量 f(u, v) 表示”我们可以把 f(u, v) 这个数字调小”。当我们沿着残量图的反向边 v→u”送水”时，实际操作是：把原边 u→v 上的流量减少若干，而不是真的让水从 v 倒灌到 u。这一步操作会让 u 的流入减少、v 的流出减少，但随后我们还会在同一条增广路径上补上相应的正向调整，因此整张网络的守恒不会被打乱。

用 1.3 节的例子来感受一下。假设当前状态是：S→A→T 走 8，S→A→B→T 走 2，S→B→T 走 8，总流 18。残量图上，A→B 这条边已满，正向残量为 0，但反向边 B→A 的残量是 2（因为 A→B 上有 2 的流量）。现在残量图里有一条路径：S→B（残量 2，因为 S→B 已用 8，容量 10）→ 反向边 B→A（残量 2）→ A→T（残量 2，因为 A→T 已用 8，容量 10）。沿这条路径增广 2 的效果是：S→B 的流量 +2，B→A 反向边对应 A→B 的流量 −2，A→T 的流量 +2。翻译成物理语言：A 之前转给 B 的那 2 吨水改走 A→T 了，B 缺的 2 吨由 S 直接补上。最终状态：S→A→T 走 10，S→B→T 走 10，A→B 走 0，总流 20。

这个例子值得反复咀嚼，因为它揭示了反向边真正的身份：它是”重新规划”的载体。算法不需要”后悔”自己做过什么决定，它只需要在残量图上找到一条包含反向边的新路径，就自动完成了”撤回旧分配 + 建立新分配”的组合动作。旧分配被撤回时，对应正向边的流量减少，反向残量也同步减少；新分配建立时，正向残量减少，反向残量增加。残量图始终准确反映”当前状态下还能做什么”。

3.3 为什么反向边是算法的灵魂

第一，没有反向边，贪心会堵死自己。1.3 节已经演示过：先走 S→A→B→T 会把总流锁死在 18，而正确答案是 20。如果没有撤回机制，任何”先来后到”的贪心都可能陷入局部最优。

第二，反向边把”重新规划”变成”找路径”。有了反向边，我们不必设计复杂的回溯逻辑，只需继续在残量图上找 S 到 T 的路径。路径上每一条边，不管是正向还是反向，操作方式完全统一：沿正向边是加流量，沿反向边是减流量。算法因此变得极其简洁。

第三，反向边让”增广”可以循环使用。一个流方案被撤回一部分后，残量图里又会重新出现对应的正向边（比如 A→B 从满变成有空余），于是未来的增广还可能再次利用这根管道。流量在管道之间”振荡”是正常现象，残量图完整记录了所有可能性。

第四，反向边是最大流最小割定理的桥梁。定理的证明依赖一个事实：当残量图中不再存在 S→T 路径时，从 S 出发可达的顶点集合恰好构成一个最小割。这个”可达集”的构造，本质上就是在残量图上做一次 BFS/DFS。没有反向边，可达集会把已经满的边排除在外，割的定义就失去了意义。

一句话总结：正向残量告诉你”还能多送多少”，反向残量告诉你”还能撤多少”，两者合在一起，才完整刻画了当前状态的所有可能动作。理解了这一点，增广路径就水到渠成了。

3.4 残量图的变化规则（增广公式）

假设我们决定沿残量图的一条路径增广 d 单位水，那么每条被经过的边都要按下面的规则更新：

如果经过的是正向边 u→v（对应原边 u→v）：f(u, v) += d；残量图里 u→v 的残量 −= d；反向边 v→u 的残量 += d。

如果经过的是反向边 v→u（对应原边 u→v）：f(u, v) −= d；残量图里 v→u 的残量 −= d；正向边 u→v 的残量 += d。

两条规则可以统一成一句话：增广 d 后，被走的那条残量边减少 d，它的对立边（同一条原边的另一个方向）增加 d。所谓”对立边”，就是”同一对顶点之间、方向相反的残量边”。这个对称性会在代码里用”反向边索引”技巧实现，第 6 节再展开。

还要注意一个看似矛盾的现象：一条原边可能同时存在正向残量和反向残量（比如容量 10、流量 6 的边，正向残量 4、反向残量 6）。在残量图里它们是两条独立的边，BFS 可以把它们当成普通边一样走。这完全合法，因为”再多送 4”和”撤回 6”是两种互不排斥的动作。

3.5 残量网络的另一种理解：状态机

如果你习惯用”状态”的眼光看算法，可以把残量网络理解成一张状态转移图：当前流是状态，残量图里每条边是一次”可行动作”，沿边增广是状态转移，动作的代价（增广量）由瓶颈决定。算法从零流状态出发，沿着可行动作一路转移，直到没有通向”汇状态”的动作为止。这样看，网络流算法和 BFS 在状态空间搜索里的地位完全一致——都是”在图上不断移动，直到无法移动”。第 4 篇里”状态空间搜索”的概念在这里再次复活，只是这次图本身是动态变化的。

好，残量网络已经就位。现在的问题变成：在残量图上找到一条从 S 到 T 的路，然后沿路增广。这条路，就是下一节的增广路径。

3.6 残量图的空间开销与工程实现

残量网络听起来像是一张”每轮增广都要重建的新图”，但在工程实现里，它并不需要单独存储。标准做法是：邻接表里每一条原边自带一条”影子”反向边，两者共享同一个增广公式，残量图就隐式地活在邻接表里。空间上，每条原边只多一个对象，总空间 O(V + E)；BFS 遍历时跳过所有 cap = 0 的边，等效于”残量图里不存在这些边”。

调试时怎么”看”残量图？写一个小函数遍历所有顶点的邻接表，打印 cap > 0 的记录即可。打印结果应该和手算的残量图完全一致——这是验证代码和理论是否咬合的最快方式。还有一个实用的自查技巧：所有反向边的 cap 之和必须等于对应原边当前的流量；如果增广代码写错了方向，这个等式会立刻露馅。

另外，增广时更新的是”这条边和它的影子”，而不是”所有指向同一目标的边”。这一点在存在反平行边、重边时尤其重要：每对正反向记录是唯一绑定的，互不越界。

4 增广路径：沿着残量图”多送一批水”

4.1 定义：残量图上从 S 到 T 的路径

给定当前流 f 和它的残量网络 G_f，如果 G_f 中存在一条从 S 到 T 的路径（每条边的残量都大于 0），这条路径就叫增广路径（Augmenting Path）。之所以叫”增广”，是因为沿它走一遍就能让总流量严格增加。

为什么一定能增加？因为路径的起点是 S、终点是 T，而路径上每条边都还”有空”：正向边还有剩余容量，反向边代表可撤回的流量。沿着路径把能送的水送出去，S 的净流出会增加，T 的净流入也会增加，中间的顶点由于”一进一出”（路径上每个中间点既有入边又有出边，增广量相同）保持守恒。总流量增加的量，就是这条路径的”瓶颈”。

这里有一个微妙的点值得展开：路径可能包含”往回走”的边（反向边），比如 S→B→A→T 里 B→A 就是往回走。从顶点序列看，路径绕了一个小弯；但从流量操作看，它完成的是”撤回 A 给 B 的水，改由 S 直接给 B”的全局调整。所以判断”有没有增广路径”绝不能只看原图，必须看残量图。

4.2 瓶颈：路径上最小的残量

路径 P 上所有边的残量取最小值，记作 Δ = min{残量(e) : e ∈ P}，这个 Δ 叫瓶颈容量（Bottleneck），也叫可增广量。沿 P 增广 Δ 后，至少有一条边会从”有空”变成”恰好满”（或反向残量恰好归零），这条边就是瓶颈边；其他边则可能还剩一些残量，留待后续增广继续使用。

为什么增广量必须取最小值而不是平均值或最大值？因为路径是串联的：S 送出的水要依次通过每一根管子，任何一根管子的容量都会卡住整条路径。就像一根水管上最细的那段决定整根管的流量上限——这是”木桶效应”在网络流里的体现。反过来，如果我们把 Δ 取得比瓶颈还大，就会有一根管子超载，违反容量约束；取得比瓶颈小，又白白浪费了容量，增广效率降低。

4.3 增广操作与守恒验证

增广操作分三步：第一，在残量图上找到一条 S→T 路径；第二，算出瓶颈 Δ；第三，对路径上每条边按 3.4 节的规则更新流量。更新完成后，原图上的每条边依然满足 0 ≤ f ≤ c（正向增广不会超过容量，反向撤回不会低于 0），每个中转站依然守恒（路径上的中间顶点一进一出，净变化为 0），而 |f| 恰好增加了 Δ。所以增广操作把可行流变成更大的可行流。

看一张具体的过程图。左边是增广前残量图里找到的路径 S→A→C→T（红色高亮），右边是增广后的新流量：

graph LR
    subgraph P1["增广前：残量图上找到路径"]
        S1["S"] -->|"2"| A1["A"]
        A1 -->|"2"| C1["C"]
        C1 -->|"2"| T1["T"]
    end
    subgraph P2["增广 Δ=2 之后：新流量"]
        S2["S"] -->|"10/10"| A2["A"]
        A2 -->|"8/8"| C2["C"]
        C2 -->|"15/15"| T2["T"]
    end

增广后，S→A、A→C、C→T 三条边全部走满，残量网络里它们各自只剩下反向边（容量分别是 10、8、15）。这时候残量图里还有别的路径吗？取决于图的其他部分——这正是下一节算法要反复回答的问题。

4.4 增广路径与”最优解判定”的关系

一个里程碑式的事实是：如果当前流对应的残量网络里不存在任何 S→T 路径，那么当前流就是最大流。这个断言并不是显然的，它正是最大流最小割定理的内容（第 7 节证明）。但先把它当作一个”停机判据”记住：算法不断地”找路径、增广、再找路径”，直到找不到路径为止；届时，最后的流就是最大流。

为什么这个判据可信？直观上，残量图里没有 S→T 路径，意味着”在不撤换任何现有流量的前提下，没有任何空余通道可以再加一批水”。剩下的可能性只剩”通过反悔重新组合”，但反向边已经包含在残量图里了——如果通过反悔能挤出更多水，残量图里就会存在一条利用反向边的 S→T 路径。所以”没有路径”等价于”无论怎么重新组合都加不了水”。

这个”找路—增广—直到无路”的框架，就是下一节 Ford-Fulkerson 方法的骨架。

4.5 一个 30 秒小练习

趁热打铁。下图是某个当前流的残量网络（数字是残量）。请问：存在增广路径吗？瓶颈是多少？提示：注意那条从 B 指向 A 的边——它很可能来自一条已经满流的 A→B 原边。

graph LR
    S["S"] -->|"3"| A["A"]
    S -->|"1"| B["B"]
    B -->|"2"| A
    A -->|"4"| T["T"]
    B -->|"3"| T

答案：存在，S→B→A→T 就是一条增广路径（B→A 是反向边），瓶颈 Δ = min(1, 2, 4) = 1。沿它增广 1 后，S→B 的流量 +1，A→B 的流量 −1，A→T 的流量 +1，总流量 +1。如果你能独立完成这个练习，说明你已经真正理解了残量图与增广路径。

4.6 找增广路径的三种策略

“在残量图里找一条 S→T 路径”本身可以有很多种实现，选择不同，算法名称和复杂度就不同：

策略一：任意路径（DFS 或标号法），对应最朴素的 Ford-Fulkerson。实现最简单，但没有复杂度保证，可能陷入大量 1 单位的小幅增广。

策略二：最短路径（BFS），对应 Edmonds-Karp。每轮找边数最少的增广路径，增广轮数 O(V·E)，总 O(V·E²)。这是本篇的主角，也是”第 4 篇 BFS 直接上岗”的地方。

策略三：最大瓶颈路径，即找”最小残量最大”的那条路径。可以用类似 Dijkstra 的贪心（按残量取最大）实现，增广轮数更少，但每轮找路更贵，适合瓶颈显著、图较小的场景。

策略四：分层图多路增广，对应 Dinic 算法。每轮先用 BFS 给残量图分层，再用 DFS 一次性推送多条路径，总复杂度 O(V²·E)，是竞赛与工程的主流选择。它和 Edmonds-Karp 共享”残量图 + 分层”思想，只是把”每轮一条路径”升级成”每轮一批路径”。

无论选哪种策略，外层循环都是同一个：找路，增广，直到无路。理解 Edmonds-Karp 之后，升级到 Dinic 只是性能优化，而不是新思想。

5 Ford-Fulkerson 与 Edmonds-Karp：从思想到算法

5.1 Ford-Fulkerson：一个朴素而伟大的框架

1956 年，L. R. Ford Jr. 和 D. R. Fulkerson 提出了最大流问题的经典解法框架，后人称之为 Ford-Fulkerson 方法。它极其简单，只有三步循环：

第一步，从零流开始（所有 f = 0）；第二步，只要残量网络 G_f 中存在 S 到 T 的路径，就任选一条，算出瓶颈 Δ，沿路增广；第三步，当残量网络不再连通 S 和 T 时，停止，当前流就是最大流。

flowchart TD
    A["初始化：所有边流量 = 0"] --> B{"残量图 G_f 中有 S 到 T 的路径？"}
    B -- "有" --> C["任选一条增广路径 P"]
    C --> D["瓶颈 Δ = P 上最小残量"]
    D --> E["沿 P 增广 Δ，更新残量图"]
    E --> B
    B -- "没有" --> F["输出当前流：这就是最大流"]

这个框架的美丽之处在于：它没有规定”任选”具体怎么选。任意选择增广路径，只要残量图里还有路，增广后总流量就严格增加；当流量是整数且容量有限时，流量最多增加有限次，算法必然终止。框架的正确性由最大流最小割定理保证，不依赖路径选择策略。

补充一个容易忽略的点：Ford-Fulkerson 的每一步操作都只依赖”当前残量图”，不依赖历史决策。这意味着它天然适合增量场景——网络结构或容量发生变化时，可以在旧流的基础上继续增广，而不必从头计算。这种”热启动”能力是很多进阶网络流算法（以及现实中的动态流量调度）的底层优势。

但”任意”也埋下了性能隐患。考虑一张图：S→A 和 S→B 容量各 1000，A→B 和 B→A 容量各 1，A→T 和 B→T 容量各 1000。如果每次增广路径都选”刚好只有 1 单位残量”的细边，比如先走 S→A→B→T（增广 1），再走 S→B→A→T（增广 1），两条路径交替出现，算法需要增广 2000 次。如果容量是 10⁹ 这种大数，而每次只增广 1，算法就会慢得不可接受；更极端地，如果容量是无理数，Ford-Fulkerson 甚至可能永不终止。这就是”任选”的代价。

怎么办？答案藏在 BFS 里：每次都选”边数最少”的增广路径。这个改进由 Edmonds 和 Karp 在 1972 年独立提出，因此叫 Edmonds-Karp 算法。它保证了增广次数至多为 O(V·E) 次（每次至少让一条边达到满流并”消失”一段时间），配合每次 BFS 的 O(E) 时间，总复杂度 O(V·E²)。这个复杂度陈述我们先用着，原理在第 5.5 节展开。

顺便说一句命名：Ford-Fulkerson 在中文教材里有时被称为”标号法”，因为最早版本通过给顶点标号（标记从哪个顶点来、增量是多少）来寻找增广路径；Edmonds-Karp 则是把”标号”规范化为 BFS，从而获得复杂度保证。理解历史命名有助于阅读老资料，但算法本身你已经完全掌握了。

5.2 手算走查一：用反向边”纠正”一次错误选择

先来一场热身走查，专治”为什么需要反向边”。网络如下（全部容量为整数）：

graph LR
    S["S"] -->|"10"| A["A"]
    S -->|"10"| B["B"]
    A -->|"2"| B
    A -->|"10"| T["T"]
    B -->|"10"| T

它的最大流是 20：S→A→T 走 10，S→B→T 走 10，A→B 完全闲置。但假设第一轮我们（故意）选了次优路径 S→A→B→T。这场走查将展示：即使走了弯路，残量图的反向边也能把流量”纠正”回来。

第 0 轮：初始状态。 所有边流量为 0，残量图就是原图，各边残量等于容量。我们选择增广路径 S→A→B→T：瓶颈 Δ = min(10, 2, 10) = 2。增广后：S→A、A→B、B→T 各增加 2。

第 1 轮：残量图。 此时 S→A 残量 8，A→B 残量 0（满），B→T 残量 8；反向边 A→S 2、B→A 2、T→B 2；S→B 残量 10，A→T 残量 10。BFS 在残量图上找最短增广路径：S→A→T 只有 2 条边（而 S→B→T 也是 2 条，BFS 按邻居顺序先到 A 就先走 S→A→T）。瓶颈 Δ = min(8, 10) = 8。增广后：S→A 总流量 10（满），A→T 流量 8。

graph LR
    S["S"] -->|"8"| A["A"]
    S -->|"10"| B["B"]
    A -->|"10"| T["T"]
    B -->|"8"| T
    A -->|"2"| S
    B -->|"2"| A
    T -->|"2"| B
    style A fill:#ffcccc,stroke:#cc0000

上图画的是第 1 轮增广前的残量图（边上数字是残量，不是流量）。红色顶点 A 提示本轮走查的焦点在 A 附近。请核对这些残量：S→A = 10 − 2 = 8；B→T = 10 − 2 = 8；A→B 正向残量 0 所以不画，反向 B→A = 2；反向 A→S = 2；反向 T→B = 2；其余 S→B = 10、A→T = 10。有没有发现规律？残量图上”少画”的边，恰恰是已经满流的正向边。

第 2 轮：残量图。 上一轮增广后，S→A 已满（残量 0），S→B 残量 10，B→T 残量 8（已被第 0 轮的 2 占掉），A→T 残量 2。BFS 找最短路径：S→B→T（2 条边）瓶颈 Δ = min(10, 8) = 8。增广后：S→B 总流量 8，B→T 总流量 10（满）。

graph LR
    S["S"] -->|"10"| B["B"]
    B -->|"8"| T["T"]
    A["A"] -->|"2"| T
    A -->|"10"| S
    T -->|"10"| B
    B -->|"2"| A
    T -->|"8"| A
    style B fill:#ffcccc,stroke:#cc0000

请再次核对残量：S→B = 10（S→B 还没被增广过，第 0 轮只走了 S→A→B→T，没走 S→B）；B→T = 10 − 2 = 8；A→T = 10 − 8 = 2；反向边 A→S = 10、T→A = 8、B→A = 2、T→B = 2；S→A 残量 0 不画。注意：此时 S→B 的流量还是 0，所以残量图里不应该出现反向边 B→S——每一条反向边都必须对应一个正流量，这是检查残量图是否画错的好方法。真正手算时建议把每条边都列全，避免遗漏路径。

第 3 轮：残量图。 现在总流 = 2 + 8 + 8 = 18。残量图里：S→B 残量 2，S→A 残量 0，A→T 残量 2，B→T 残量 0，A→B 残量 0；反向边有 B→A（2，对应 A→B 上的 2 流量）、A→S（10）、T→A（8）、B→S（8）、T→B（10）。BFS 还能找到路径吗？能：S→B（残量 2）→ B→A（反向，残量 2）→ A→T（残量 2），路径 S→B→A→T，瓶颈 Δ = 2。沿它增广的效果：S→B 流量 +2；反向边 B→A 对应 A→B 流量 −2；A→T 流量 +2。

graph LR
    S["S"] -->|"2"| B["B"]
    B -->|"2"| A["A"]
    A -->|"2"| T["T"]
    A -->|"10"| S
    B -->|"8"| S
    T -->|"10"| B
    T -->|"8"| A
    style B fill:#ccffcc,stroke:#009900
    style A fill:#ccffcc,stroke:#009900

增广后总流 = 18 + 2 = 20。最终流量：S→A = 10，S→B = 10，A→T = 10，B→T = 10，A→B = 0。S 出 20，T 入 20，一切守恒。残量图里 S 只能到达自己（S→A 与 S→B 残量都为 0），不再有增广路径，算法终止，得到最大流 20。

这场走查最值得记住的一幕在第 3 轮：路径上明明画着一条”从 B 到 A”的反向边，但真实效果是”把 A→B 上的 2 撤掉，让 A 的水改走 A→T，让 B 的水由 S 直接供给”。整个纠正过程没有推翻任何历史决策，只是沿着残量图又走了一条路。

5.3 手算走查二：Edmonds-Karp 的完整四轮

第二场走查展示 Edmonds-Karp 的标准行为：每轮用 BFS 找边数最少的增广路径，一共四轮。网络如下，中间层有两个顶点 C、D，形成”菱形”结构：

graph LR
    S["S"] -->|"4"| A["A"]
    S -->|"4"| B["B"]
    A -->|"3"| C["C"]
    A -->|"3"| D["D"]
    B -->|"3"| C
    B -->|"3"| D
    C -->|"4"| T["T"]
    D -->|"4"| T

先预判一下最大流：S 能给出 4 + 4 = 8，T 能收下 4 + 4 = 8，中间四个”菱形”通道总容量 3 × 4 = 12，足以承担 8，所以最大流应该是 8。我们来看 Edmonds-Karp 能不能通过四轮增广拿到 8。

第 1 轮。 初始残量图就是原图。BFS 从 S 出发，邻居 A 在前：S→A（残量 4）→ C（残量 3）→ T（残量 4），路径 S→A→C→T，瓶颈 Δ = min(4, 3, 4) = 3。增广 3：S→A 3/4，A→C 3/3（满），C→T 3/4。

第 2 轮。 残量图：S→A 残量 1，S→B 残量 4，A→C 残量 0，A→D 残量 3，B→C 残量 3，B→D 残量 3，C→T 残量 1，D→T 残量 4；反向边 C→A 3、A→S 3、T→C 3。BFS 从 S 出发：S→A（1）→ D（3）→ T（4），路径 S→A→D→T，瓶颈 Δ = min(1, 3, 4) = 1。增广 1：S→A 4/4（满），A→D 1/3，D→T 1/4。

graph LR
    S["S"] -->|"1"| A["A"]
    S -->|"4"| B["B"]
    A -->|"3"| D["D"]
    B -->|"3"| C["C"]
    B -->|"3"| D
    C -->|"1"| T["T"]
    D -->|"4"| T
    C -->|"3"| A
    A -->|"3"| S
    T -->|"3"| C
    style A fill:#ccffcc,stroke:#009900
    style D fill:#ccffcc,stroke:#009900
    style T fill:#ccffcc,stroke:#009900

第 3 轮。 残量图：S→A 残量 0，S→B 残量 4，A→D 残量 2，D→T 残量 3，B→C 残量 3，B→D 残量 3，C→T 残量 1；反向边 D→A 1、A→S 4、T→D 1、C→A 3、T→C 3。BFS：S→B（4）→ C（3）→ T（1），瓶颈 Δ = min(4, 3, 1) = 1。增广 1：S→B 1/4，B→C 1/3，C→T 4/4（满）。

第 4 轮。 残量图：S→B 残量 3，B→C 残量 2，B→D 残量 3，A→D 残量 2，D→T 残量 3，C→T 残量 0；反向边 T→C 4、C→B 1、D→A 1、A→S 4、T→D 1、C→A 3。BFS：S→B（3）→ D（3）→ T（3），瓶颈 Δ = 3。增广 3：S→B 4/4（满），B→D 3/3（满），D→T 4/4（满）。

graph LR
    S["S"] -->|"3"| B["B"]
    B -->|"2"| C["C"]
    B -->|"3"| D["D"]
    D -->|"3"| T["T"]
    T -->|"4"| C
    C -->|"1"| B
    D -->|"1"| A["A"]
    C -->|"3"| A
    style B fill:#ccffcc,stroke:#009900
    style D fill:#ccffcc,stroke:#009900
    style T fill:#ccffcc,stroke:#009900

四轮增广后总流 = 3 + 1 + 1 + 3 = 8。最终流量：S→A = 4（A→C 3 + A→D 1），S→B = 4（B→C 1 + B→D 3），C→T = 4，D→T = 4。残量图上再做一次 BFS：S 的邻居 A、B 残量都是 0，可达集只有 {S}，找不到 S→T 路径，算法终止。最大流 = 8，与预判一致。

注意第 2 轮只增广了 1：因为 S→A 只剩 1，尽管 A→D 和 D→T 都很宽裕。这正是”瓶颈”的含义——路径的增量受制于最窄的那段。而第 4 轮 S→B→D→T 又拿下了 3，因为 S→B 剩余 3 恰好够用。四轮下来，所有从 S 出发的管道都被榨干，算法自然结束。

5.4 两场走查给我们的三个启发

第一，增广路径不必是”原图路径”。走查一第 3 轮的路径包含反向边，走查二每轮都只走原图边；两种路径在残量图里地位完全平等，算法不需要区分。

第二，每次增广都严格增加总流量，增量等于瓶颈 Δ；当 Δ 越来越小、路径越来越长时，说明网络正在被逐渐填满，接近尾声。

第三，终止条件非常干净：残量图上 S 不可达 T，等价于”从 S 出发的所有正向残量通道全部枯竭”。此时我们不仅得到了最大流，还免费得到了一张最小割——第 7 节揭晓。

5.5 为什么 BFS 让算法变快：Edmonds-Karp 的复杂度直觉

任选增广路径的 Ford-Fulkerson 可能非常慢，而 Edmonds-Karp 用 BFS 保证每轮选”边数最少”的路径，从而把增广轮数限制在 O(V·E)。为什么”最短”这么神奇？

关键性质是：残量图里 S 到任意顶点的最短距离（按边数）在增广过程中只会单调不减。增广可能会产生新的反向边，这些反向边看起来是”新路”，但 BFS 的层序特性保证它们不会让最短距离变短。于是，从 S 到 T 的最短距离 d 只会逐步增大；而在距离固定为 d 的期间，每次增广至少会”废掉”一条当前距离下的瓶颈边（这条边残量归零），它至少要等到 S→T 距离变长之后才可能重新有用。综合起来，每个距离值 d 最多对应 O(E) 次增广，距离最多从 1 涨到 V−1，所以总增广次数 O(V·E)。每次 BFS 是 O(E)，总时间 O(V·E²)。这个证明的完整细节超出本文范围，但直觉一定要有：BFS 让每次增广都”物有所值”，不允许算法在细边上磨洋工。

从工程角度，Edmonds-Karp 对大多数教学与竞赛场景已经够用；追求更高性能时还有 Dinic（分层图 + 当前弧）、ISAP、Push-Relabel 等进阶算法，它们的思想都是在这个框架上做优化。本篇聚焦 Edmonds-Karp，把”残量图 + BFS + 增广”的内功练扎实。

5.6 整数容量为什么重要：一个数值例子

为什么全篇反复强调整数容量？用一个具体例子感受一下。考虑网络：S→A 和 S→B 容量 100，A→B 和 B→A 容量 1，A→T 和 B→T 容量 100。最大流是 200，Edmonds-Karp 用两轮就能完成（S→A→T、S→B→T，各 100）。但如果用”任意路径”的 Ford-Fulkerson 且每次都选细边，路径会交替走 S→A→B→T 和 S→B→A→T，每轮只增广 1，一共需要 200 轮——整整慢 100 倍。把容量换成 10⁹，差距就更可怕了。

更极端的情况是无理数容量：存在构造出的网络（经典例子是容量按等比数列 1, r, r², … 设置，其中 r 是某个特殊无理数），Ford-Fulkerson 每次只增广一点点，永远无法终止。Edmonds-Karp 的 BFS 最短路径策略彻底消灭了这种病态行为，这也是它被称为”算法”而不是”方法”的原因。

工程实践里，容量几乎总是整数（带宽、人数、件数、场次），因此整数假设很少成为限制。如果遇到浮点容量，常见的处理是统一放大成整数（比如乘以 10⁶ 再取整），或者改用支持浮点的推进-重标号算法。

5.7 两场走查的对照表

把两场手算并排放在一起，差异与共性一目了然：

轮次	走查一：反向边纠正	走查二：菱形网络
第 1 轮	路径 S→A→B→T，瓶颈 2	路径 S→A→C→T，瓶颈 3
第 2 轮	路径 S→A→T，瓶颈 8	路径 S→A→D→T，瓶颈 1
第 3 轮	路径 S→B→T，瓶颈 8	路径 S→B→C→T，瓶颈 1
第 4 轮	路径 S→B→A→T（含反向边），瓶颈 2	路径 S→B→D→T，瓶颈 3
总流量	2 + 8 + 8 + 2 = 20	3 + 1 + 1 + 3 = 8
终止判据	S→A、S→B 残量均为 0	S→A、S→B 残量均为 0
最小割	X = {S}，割容量 20	X = {S}，割容量 8

两场走查的共同点是：每一轮都先 BFS（或任选路径）找到一条增广路径，算出瓶颈，再同步更新正反向残量；终止时从 S 出发的管道全部枯竭，最小割恰好落在 S 的出边上。差异在于走查一第 4 轮用到了反向边，走查二则四轮都走原图边——这说明反向边不是”一定会用”的机制，而是”必要时可用”的保险。

把这张对照表带到第 6 节：写代码时，可以用它逐轮核对程序打印的路径与瓶颈。若某轮对不上，八成是增广公式的正负号写反了。

6 代码实现：邻接表 + 反向边索引

6.1 存储设计：每一条边都带一个”影子”

写代码之前先想清楚存储。网络流算法里最常用的结构是邻接表 + 反向边索引：

对每一条有向边 u→v，我们同时创建两条记录：正向记录存在 graph[u] 里，反向记录存在 graph[v] 里。正向记录里存目标 v、当前残量 cap、以及”我的反向记录在 graph[v] 中的下标 rev”；反向记录同理指向正向记录。为什么要存下标而不是直接存引用？因为数组在增广过程中不需要频繁增删，用下标可以在 O(1) 时间内找到”我的对立边”，实现 3.4 节的对称更新。

残量用”当前剩余容量”表示。正向边初始化为 c，反向边初始化为 0；当沿正向边增广 d 时，正向 cap 减 d、反向 cap 加 d——反向边”cap”的含义正是可撤回量 f。当沿反向边增广 d 时，操作自动对称。这样，代码里根本不需要维护单独的 f 数组：残量 cap 已经把 f 编码进去了（正向边 f = c − cap，反向边 cap = f）。

为什么需要”影子”边？因为残量网络和原图共享顶点集，但边集合随流量变化。如果每次增广都动态重建整张残量图，代价太高；用”每对边互为影子、增广时同步更新”的方式，残量图就隐式地活在邻接表里，BFS 和增广都只需要读 cap 字段。

6.2 完整代码：Edmonds-Karp

下面是用 TypeScript 风格写的完整实现。顶点编号 0..n−1，源是 0，汇是 n−1；图用邻接表 graph 存储：

// 一条边：to 是目标顶点，cap 是当前残量，rev 是对立边在对方邻接表中的下标
type Edge = { to: number; cap: number; rev: number };

class MaxFlow {
  private graph: Edge[][] = [];

  constructor(private n: number) {
    for (let i = 0; i < n; i++) this.graph.push([]);
  }

  // 添加一条容量为 cap 的有向边 u -> v，并自动创建反向边
  addEdge(u: number, v: number, cap: number) {
    const forward: Edge = { to: v, cap, rev: this.graph[v].length };
    const backward: Edge = { to: u, cap: 0, rev: this.graph[u].length };
    this.graph[u].push(forward);
    this.graph[v].push(backward);
  }

  // BFS：在残量网络上找一条 s 到 t 的路径，把路径信息写进 parent 数组
  private bfs(s: number, t: number, parent: number[], parentEdge: number[]): boolean {
    const visited = new Array<boolean>(this.n).fill(false);
    const queue: number[] = [s];
    visited[s] = true;
    let head = 0;

    while (head < queue.length) {
      const u = queue[head++];
      for (let i = 0; i < this.graph[u].length; i++) {
        const e = this.graph[u][i];
        if (!visited[e.to] && e.cap > 0) {
          visited[e.to] = true;
          parent[e.to] = u;        // 记录从哪个顶点来
          parentEdge[e.to] = i;    // 记录从哪个邻接表下标来
          if (e.to === t) return true; // 到达汇，提前结束
          queue.push(e.to);
        }
      }
    }
    return false; // 残量网络里 s 到不了 t
  }

  // 主算法：不断找增广路径并增广，直到没有路径
  maxFlow(s: number, t: number): number {
    let flow = 0;
    const parent = new Array<number>(this.n).fill(-1);
    const parentEdge = new Array<number>(this.n).fill(-1);

    while (this.bfs(s, t, parent, parentEdge)) {
      // 1. 从 t 沿着 parent 回溯，找到路径上的最小残量（瓶颈）
      let bottleneck = Infinity;
      for (let v = t; v !== s; v = parent[v]) {
        const e = this.graph[parent[v]][parentEdge[v]];
        bottleneck = Math.min(bottleneck, e.cap);
      }

      // 2. 沿着路径更新每条边及其反向边
      for (let v = t; v !== s; v = parent[v]) {
        const u = parent[v];
        const e = this.graph[u][parentEdge[v]];
        e.cap -= bottleneck;              // 正向残量减少
        this.graph[v][e.rev].cap += bottleneck; // 反向残量增加
      }

      flow += bottleneck; // 总流量增加瓶颈那么多
    }

    return flow;
  }
}

6.3 逐行解释

Edge 类型。to 是这条残量边指向的顶点；cap 是当前剩余容量（正向边剩多少能加、反向边剩多少能撤）；rev 是对立边在目标顶点邻接表中的下标。请特别理解 rev 的含义：正向边 u→v 的 rev 指向 graph[v] 里的反向边，反向边的 rev 又指回 graph[u] 里的正向边，两者互相咬合。

构造函数。按顶点数 n 初始化 n 个空数组。邻接表方案在稀疏图上节省内存，在稠密图上也能工作，是网络流代码的事实标准。

addEdge(u, v, cap)。这是全篇代码最需要仔细读的三行。设正向边在 graph[u] 中的下标是 this.graph[u].length（压入前的长度）；反向边在 graph[v] 中的下标是 this.graph[v].length。于是正向边的 rev 应该指向”反向边在 graph[v] 中的下标”，即压入反向边之前 graph[v] 的长度；反向边的 rev 应该指向”正向边在 graph[u] 中的下标”，即压入正向边之前 graph[u] 的长度。代码先构造 forward 和 backward 两个对象、再分别 push，顺序上利用 push 前后 length 的差值，恰好让两者互指。一个常见陷阱是：如果先 push 正向边再构造反向边，正向边的 rev 就会算错；所以一定要在 push 之前就记录对方的下标。

bfs。visited 防止重复入队；queue 配合 head 指针实现队列（用 shift() 也可以，但每次 O(n) 很浪费，head 指针是常见优化）。从 s 开始，逐层扩散；对每个未访问且残量大于 0 的邻居 e.to，记录 parent 和 parentEdge 后入队。如果到达 t，立即返回 true——注意此时不必把整张图遍历完，BFS 已经找到一条最短路径（边数最少）。parent 数组记录”从哪个顶点来”，parentEdge 记录”从那个顶点的邻接表第几个下标来”，两者配合才能唯一确定路径上的边。

为什么 BFS 找到的一定是边数最少的路径：这是第 4 篇的核心结论——BFS 按层扩散，第一次访问到 t 时，走过的边数就是最短距离。Edmonds-Karp 正是依赖这一点才拥有 O(V·E²) 的复杂度保证。

主循环。while (bfs(...)) 每成功一次就完成一轮增广。第一段回溯：从 t 沿着 parent 一路回到 s，逐条取出路径上的边，取最小残量作为 bottleneck。第二段回溯：再次从 t 走到 s，对每条边 e 执行 e.cap -= bottleneck，并通过 e.rev 找到对立边执行 += bottleneck。由于正向边和反向边共用同一个对象对，增广操作天然对称，不需要写两套逻辑。最后 flow += bottleneck。

为什么要用 e.rev 而不是”找一条名字带 reverse 的边”：因为残量网络里一对方向相反的边在内存里是紧挨着创建的，用下标互指可以把”找对立边”变成 O(1)。如果每次更新都线性扫描目标顶点的邻接表，总复杂度会多一个 E 因子，得不偿失。

关于 parent 数组是否需要重置：每次 BFS 都会重新给 visited 和 parent 赋值，主循环里不需要手动清空；找不到路径时 BFS 返回 false，循环自然结束。终止后 parent 数组正好记录着最后一次 BFS 的访问结构——第 7 节求最小割时，我们还要再利用它一次。

关于整数与实数容量：代码假设 cap 是整数（比较、加减都精确）。如果容量是浮点数，Edmonds-Karp 依然能跑，但可能因为浮点误差出现”瓶颈极小但非零”的增广；实际应用中通常把容量放大成整数或直接用有理数处理。

6.4 复杂度：O(V·E²)

Edmonds-Karp 的时间复杂度是 O(V·E²)，其中 V 是顶点数、E 是边数。拆开看：每一轮增广做一次 BFS，耗时 O(E)；增广轮数至多 O(V·E)（理由见 5.5 节的”最短距离单调不减”论证）；合起来 O(V·E²)。空间复杂度 O(V + E)，主要是邻接表、visited、parent 数组。

对稠密图（E ≈ V²），复杂度会退化到 O(V⁵)，所以实际工程中常用 Dinic 等更快的算法；但对绝大多数教学例题与中等规模的图，Edmonds-Karp 简单可靠、不易写错，是理解网络流的完美第一站。

6.5 代码自测：把 5.3 节的例子跑一遍

把 5.3 节的菱形网络输入代码：顶点共 6 个（S、A、B、C、D、T，编号 0..5），依次调用 addEdge：0→1（S→A，4）、0→2（S→B，4）、1→3（A→C，3）、1→4（A→D，3）、2→3（B→C，3）、2→4（B→D，3）、3→5（C→T，4）、4→5（D→T，4）。然后调用 maxFlow(0, 5)，返回值应为 8。你可以亲手在浏览器控制台或 Node.js 里验证，也可以把这段代码改造成带打印的版本，观察每轮 bottleneck 依次是 3、1、1、3——正好对应手算走查的四个数字。能把这个对应上，说明代码和理论完全咬合了。

再自测一个反向边场景：5.2 节的图（S→A 10、S→B 10、A→B 2、A→T 10、B→T 10），maxFlow 返回 20；如果把 A→B 的容量改成 0（即删掉这条边），maxFlow 依然返回 20——因为 S→A 10 全走 A→T、S→B 10 全走 B→T 就够了。这说明 A→B 在这张图里不是关键边；把它改大或改小都不影响最大流。想要验证反向边确实被用到，可以打印每轮增广路径，观察第 3 轮路径里出现 B→A。

6.6 常见实现错误清单

第一，忘了创建反向边。addEdge 里只 push 正向边、不 push 反向边，会导致增广时 e.rev 越界。第二，rev 下标算错。先 push 再记录 length，会让正向边指向错误的下标；一定要在 push 前计算。第三，BFS 里用 shift() 且队列很大。功能没错，但每轮 O(V) 的移动会让总复杂度多一个因子，建议用 head 指针。第四，visited 标记在出队时才做。同一个顶点可能被多个邻居入队两次，导致路径记录被覆盖，应该”入队即标记”。第五，bottleneck 初始化为 0。应该初始化为正无穷（或一个足够大的数），否则永远为 0。第六，增广循环写错回溯终点。必须走到 v === s 为止，写成 v >= 0 会在 s 处访问 parent[-1]。

这些错误几乎每个人都会至少踩一次。建议写完代码后用两个手算例子做测试：一个有反向边、一个没有，输出每轮路径和 bottleneck，与手算对照。

6.7 单元测试：三张图快速验证

写完代码后，别急着提交，先用三张巴掌大的图做单元测试，每个都能手工验证：

用例一（单边）：只有 S→T 容量 5。答案 5。测的是 addEdge 和最基本的主循环。

用例二（并行路径）：S→A 3、A→T 3、S→B 2、B→T 2。答案 5。两条路径互不干扰，每轮增广一条，总共两轮。

用例三（反向边场景）：5.2 节的图（S→A 10、S→B 10、A→B 2、A→T 10、B→T 10）。答案 20。它考验 BFS 能否找到包含反向边的路径，以及增广公式的对称性。

用例四（不可达）：S 只有一个出边 S→A 容量 5，但 A 没有任何出边。答案 0。BFS 第一轮就失败，主循环一次都不执行，flow 保持 0——这测试了”没有增广路径”的边界。

用例五（多轮小图）：5.3 节的菱形图。答案 8，且可打印每轮 bottleneck 依次为 3、1、1、3。这测试了多轮增广与残量图更新的连续性。

建议在代码里加一个断言：最终残量图上从 S 出发做 BFS，T 必须不可达；再把可达集对应的割容量求和，必须等于返回值。这两个断言同时成立时，代码几乎不可能写错。

7 最大流最小割定理：最窄的瓶颈就是最大流量

7.1 割：把网络切成两块

现在登上本篇的理论高峰。先定义割（Cut）。把顶点集合 V 分成两个非空子集 X 和 Y，要求源 S ∈ X、汇 T ∈ Y（X、Y 无交集且并集为 V）。从 X 中的顶点指向 Y 中顶点的所有边，合起来称为这个割的割边集，记作 δ(X)；割边集上所有边的容量之和，叫割容量，记作 c(X, Y) = Σ_{u∈X, v∈Y} c(u, v)。

注意两个易错点。第一，割只统计从 X 到 Y 的边，不统计从 Y 到 X 的边——因为水只能从源一侧流向汇一侧，反向的边对”切断供水”没有帮助。第二，割的容量由边的容量决定，与当前流量无关；它是网络的固有属性，而流量是动态分配的。

下面这张图演示一个割：虚线把图分成 X = {S, A, B} 和 Y = {T}。割边是 A→T（容量 8）和 B→T（容量 10），割容量 = 8 + 10 = 18。X 内部的边 S→A、S→B、A→B 都不算割边：

graph LR
    subgraph X["X = {S, A, B}"]
        S["S"] -->|"10"| A["A"]
        S -->|"10"| B["B"]
        A -->|"2"| B
    end
    subgraph Y["Y = {T}"]
        T["T"]
    end
    A -->|"8"| T
    B -->|"10"| T

这个割容量 18 和 1.1 节的最大流相等，是巧合吗？不是，这正是最大流最小割定理的预告。再换个割试试：X = {S}，割边是 S→A（10）+ S→B（10）= 20；X = {S, A}，割边是 S→B（10）+ A→B（2）+ A→T（8）= 20；X = {S, B}，割边是 S→A（10）+ B→T（10）= 20（A→B 从 Y 到 X，不算）。所以 18 是所有割里的最小值，它恰好等于最大流。

7.2 任意流 ≤ 任意割：弱对偶

定理（弱对偶）：对任意可行流 f 和任意割 (X, Y)，有 |f| ≤ c(X, Y)。

证明非常短，靠的是流量守恒：把 X 中所有顶点的守恒方程加起来。除 S 外，X 中每个顶点 v 满足”流入 = 流出”，而 S 的净流出是 |f|。把所有方程相加，X 内部边成对抵消（u→v 既是 u 的流出也是 v 的流入），剩下的恰好是”从 X 流到 Y 的总量 − 从 Y 流到 X 的总量 = |f|“。前者 ≤ Σ_{u∈X,v∈Y} c(u,v) = c(X,Y)，后者 ≥ 0，所以 |f| ≤ c(X,Y)。证毕。

这个不等式告诉我们：任何割都是一堵墙，任何流都穿不过这堵墙。因此最大流的值不可能超过最小割的容量。真正令人惊讶的是等号成立：

最大流最小割定理（Max-Flow Min-Cut Theorem）：在任何流网络中，最大流的值等于最小割的容量：max |f| = min c(X, Y)。

也就是说，“最多能送多少水”和”最窄的一堵墙能挡住多少水”永远相等。这个定理由 Ford 和 Fulkerson 在证明其算法时一并得到，是组合优化里最漂亮的”对偶”结果之一。

直觉：设想网络已经达到最大流状态。此时残量图中 S 到 T 不连通（否则还能增广）。令 X 为残量图中从 S 出发可达的顶点集合，Y = V − X。那么对任意 u ∈ X、v ∈ Y，残量图里不能有边 u→v（否则 v 可达），于是正向残量 c(u,v) − f(u,v) = 0，即 f(u,v) = c(u,v)——所有跨越割的边都满流。同时，任何从 Y 到 X 的边 v→u，若 f(v,u) > 0，残量图里会有反向边 u→v，矛盾于 u 可达而 v 不可达，所以 f(v,u) = 0。代回弱对偶证明中的等式：|f| = Σ_{u∈X,v∈Y} f(u,v) − Σ_{v∈Y,u∈X} f(v,u) = Σ c(u,v) = c(X,Y)。于是当前流达到上界，就是最大流，而 (X, Y) 恰好是一个容量等于 |f| 的割，从而是最小割。这同时完成了”算法终止时流最大”和”最大流=最小割”两个结论。

7.3 从最后一次 BFS 读出最小割

这个证明附带了一个极其实用的副产品：求最小割不用单独写算法，最后一次失败的 BFS 已经给出了答案。

具体做法：Edmonds-Karp（或任何增广算法）终止后，在最终残量图上从 S 再做一次 BFS（或 DFS），得到可达集 X。那么最小割就是 (X, V−X)，割边是从 X 指向 V−X 的所有原图边。为什么？因为终止时 S 到 T 不连通，所以 T ∉ X；而按上面的证明，所有从 X 到 Y 的原边都满流、所有从 Y 到 X 的原边都零流，割容量恰好等于最大流。

用 5.2 节的走查一验证：终止时 S→A、S→B 残量都是 0，BFS 可达集 X = {S}，割边 S→A（10）+ S→B（10）= 20 = 最大流。用 5.3 节的走查二验证：可达集同样是 {S}，割边 S→A（4）+ S→B（4）= 8 = 最大流。再用手算验证 1.1 节的图：最终流量是 S→A 10、S→B 8、A→T 8、A→B 2、B→T 10；残量图上 S→A 满（残量 0）、S→B 残量 2（可达 B）、B→A 反向残量 2（可达 A）、A→T 满、B→T 满，所以 X = {S, A, B}，割边 A→T（8）+ B→T（10）= 18 = 最大流。三种情况全部对上。

下面画一张”最小割”示意图：虚线把 X 和 Y 分开，穿越虚线的边就是从 X 到 Y 的割边，每条都已满流：

graph LR
    subgraph X["X：残量图中 S 可达的集合"]
        S["S"]
        A["A"]
        B["B"]
        S -->|"10/10 满"| A
        S -->|"8/10"| B
        A -->|"2/2 满"| B
    end
    subgraph Y["Y：其余顶点"]
        T["T"]
    end
    A -->|"8/8 满"| T
    B -->|"10/10 满"| T

注意：S→A 已满流（残量 0），S 在残量图里不能直接到达 A，但可以通过 S→B（残量 2）再走反向边 B→A（残量 2）到达 A，所以 A 依然在可达集 X 里。这正是反向边在求最小割时也在起作用的例证——如果忽略反向边，我们可能会错误地以为 A 在 Y 侧。

7.4 定理的意义：不止是理论装饰

最大流最小割定理的价值远超”证明算法正确”。它把一个最大化问题和最小化问题连接起来，让无数看似无关的问题可以互相转化：

第一，判定与构造合一。要证明某个流是最大流，只需找到容量相等的割；要证明某个割是最小割，只需找到流量相等的流。这在竞赛与面试中非常实用：构造”上界 + 方案”是常见证明套路。

第二，对偶视角。割可以理解成”破坏网络最便宜的方式”——要切断 S 到 T 的所有通路，最少要拆除多少容量？答案是最大流量。这直接对应现实中的网络可靠性、最小截断、关键设施评估等问题。

第三，为第 15 篇埋伏笔：二分图最大匹配、最小点覆盖、最大独立集等经典问题，都可以通过”构造一个流网络，再读最小割”来求解。König 定理（二分图中最大匹配 = 最小点覆盖）本质上就是最大流最小割定理在二分图上的化身。下一篇我们会专门展开。

7.5 最大流结果自查清单

手算或编程得到”最大流”后，如何确认它真的最大？按下面五步自查，缺一不可：

检查一：容量约束。 逐条边验证 0 ≤ f ≤ c。只要有一条边超容，方案就是非法的。

检查二：流量守恒。 对除 S、T 外的每个顶点，流入 = 流出。这一步最能发现”路径没连上”或”增广少加了一条边”的错误。

检查三：残量图无路。 用当前流构建残量图，从 S 做一次 BFS，确认 T 不可达。这是”最大”的充分条件。

检查四：构造等容量割。 把检查三的可达集记为 X，计算割容量 c(X, V−X)，它必须等于 |f|。两者相等时，弱对偶立即告诉你 |f| 已经是上界。

检查五：源汇对账。 S 的净流出 = T 的净流入 = |f|。虽然它由守恒自动保证，但单独核对一遍可以抓住记账错误。

这五步也是面试中”证明你的答案正确”的标准套路：给出合法方案（检查一二），再给出紧的上界（检查三四），完美闭环。

8 应用：从水管到整个算法世界

8.1 二分图最大匹配：为第 15 篇埋下的种子

最大流最著名的应用之一是把二分图最大匹配转换成最大流。二分图的顶点分成左部 L 和右部 R，边只在 L、R 之间；匹配是选一组两两不共端点的边，最大匹配就是边数最多的匹配。怎么用网络流求？

构造一个流网络：加一个超级源 S*，从它向每个左部顶点连容量 1 的边；把每条原匹配边 L→R 方向化（容量 1）；再从每个右部顶点向超级汇 T* 连容量 1 的边。然后求最大流。由于每条”单位容量”路径 S*→L→R→T* 恰好对应一条匹配边，而每个左部顶点入边容量 1、每个右部顶点出边容量 1，所以一个整数值的流自动对应一个合法匹配，流的值就是匹配的边数；最大流即最大匹配。

graph LR
    SS["S* 超级源"] -->|"1"| L1["左1"]
    SS -->|"1"| L2["左2"]
    SS -->|"1"| L3["左3"]
    L1 -->|"1"| R1["右1"]
    L1 -->|"1"| R2["右2"]
    L2 -->|"1"| R2
    L3 -->|"1"| R2
    L3 -->|"1"| R3["右3"]
    R1 -->|"1"| TT["T* 超级汇"]
    R2 -->|"1"| TT
    R3 -->|"1"| TT

这张图的最大流是多少？如果最大匹配是 3（左1-右1、左2-右2、左3-右3），网络最大流就是 3。更重要的是，最小割的”可达集”还能帮我们找到最小点覆盖——这正是 König 定理的内容，也是第 15 篇《二分图匹配与综合实战》的主角。今天先埋下这颗种子：匹配问题的建模口诀是”源连左、右连汇、边做单位容量”。

为什么这个建模是”正确的”？关键在于整数性：网络里所有容量都是 1，Edmonds-Karp 每轮增广的瓶颈 Δ 也是 1，所以最终流是整数值的”0/1 流”；把每个流值为 1 的单位路径还原成匹配边，由于左部入流最多 1、右部出流最多 1，这些边两两不共端点，恰好是一个匹配。反过来，任何匹配都能翻译成这样的 0/1 流。于是最大匹配和最大流一一对应。

8.2 任务分配：人、任务、容量

经典的任务分配问题：有 m 个工人和 n 个任务，每个工人只能做某些任务，且每个任务只需要一个人，每个人最多做一个任务。这就是二分图匹配。如果工人 i 做任务 j 的”效率”有上限 a(i,j)，并且每个工人可以做多个任务、每个任务也可以由多个人分担，就变成运输问题：S* 连工人（容量 = 工人的总工时上限），工人连任务（容量 a(i,j)），任务连 T*（容量 = 任务的需求量）。最大流给出”最多能完成多少工作量”，而费用最小化版本（最小费用最大流）则在之后的进阶篇再讲。

另一种变体是调度：任务在特定时间窗口内可执行，把时间轴离散成槽位，任务连可用的时间槽，容量 1，再连汇；最大流直接回答”能否全部排下”。还可以加入”每个任务最多占用两个槽位”之类的约束，通过调整边的容量来表达。这就是网络流建模的魅力：把约束翻译成容量，把目标翻译成流量。

再举一个更贴近生活的例子：多台服务器处理请求。每台服务器单位时间能处理一定数量的请求（容量），每个请求只能由特定几台服务器处理（连边），问单位时间内最多处理多少请求？建模和任务分配完全一样。很多看似毫无关系的调度/分配问题，最后都会落到”能不能找到一个满流”上。

8.3 项目选择：带权闭合子图

再高级一点的应用是项目选择（Project Selection）：有一批项目，每个项目有收益（可能为负），项目之间存在依赖关系（选了 A 必须选 B），问选哪些项目收益最大。建模方法：源连所有正收益项目（容量 = 收益），所有负收益项目连汇（容量 = −收益），依赖边”项目 → 前置项目”容量 +∞，然后求最小割。直观理解：割边要么砍掉正收益（放弃项目），要么砍掉负成本（承担损失），最小割对应最优选择。

这个模型的正确性同样由最大流最小割定理保证：任何从 S 到 T 的路径都代表”选了项目却拒绝它的依赖”这种非法方案，+∞ 容量保证最小割绝不会切断这类边；剩下的割代价恰好是”放弃的正收益 + 承担的负成本”，最小化它等于最大化净收益。这个模型在图像分割、开矿规划、供应链决策里都有应用。

下面画一个迷你示例：项目 P1 收益 5、P2 收益 4、P3 成本 3（负收益），依赖 P3 是 P1 和 P2 的共同前置。建模后，源连 P1、P2（容量 5、4），P3 连汇（容量 3），P1→P3、P2→P3 容量 ∞：

graph LR
    S["S 源"] -->|"5"| P1["P1 收益 5"]
    S -->|"4"| P2["P2 收益 4"]
    P1 -->|"∞"| P3["P3 成本 3"]
    P2 -->|"∞"| P3
    P3 -->|"3"| T["T 汇"]

这个例子的最优选择显然是 P1、P2、P3 全选：总正收益 5 + 4 = 9，承担成本 3，净收益 9 − 3 = 6。用网络流语言验证：全选对应割 X = {S, P1, P2, P3}，割边只有 P3→T（容量 3），割容量 = 3；此时最大流 = 3（S 送出的水被 P3→T 卡住），正好等于最小割，而净收益 = 总正收益 − 最小割 = 6。反过来，如果放弃 P1（不选它），割要切断 S→P1，代价 5，净收益变成 9 − 5 − 3 = 1，明显更差。通过最小割，我们同时得到了”选哪些项目”和”最优收益”。

8.4 图像分割：一句话版本

图像分割里，每个像素是顶点，相邻像素之间连”不相似度”边，前景/背景先验分别连源和汇；最小割把像素分成两类，割掉的边恰好对应分割边界上的代价，于是最小割 = 代价最小的分割。这类”能量最小化”方法曾是计算机视觉的主流工具，其核心就是今天学的最大流最小割定理。

8.5 更多现实场景一览

交通调度（路网容量）、电网潮流（输电容量）、通信网络（链路带宽）、紧急疏散（出口容量）、棒球淘汰判定（组合优化建模）、矩阵平衡、供应链库存……凡是有”供应—中转—需求 + 容量上限”结构的优化问题，几乎都可以尝试用网络流建模。学习网络流的投资回报率非常高：一个模型，半个算法世界。

8.6 棒球淘汰问题：多源多汇实战

网络流最经典的”烧脑”应用之一是棒球联赛的淘汰判定：赛季还剩若干场比赛，问某支球队还有没有可能夺冠（或至少并列第一）。直接枚举所有比赛结果是指数级的，但建模成最大流只需要几行。

设目标队是 T0，它最多还能拿到 W0 + r0 胜（W0 是已胜场数，r0 是它剩余比赛数）。其他每支队伍 i 最多能赢 W0 + r0 − Wi 场（Wi 是它当前胜场数）。现在问：剩余比赛能不能安排出一个结果，使得所有队伍的最终胜场都不超过 T0 的上限？如果能，T0 还没有被淘汰。

建模如下：新建超级源 S*，为每一场”非 T0 参与的剩余比赛”建一个节点，S* 连它（容量 1，即这场比赛有 1 个胜场要分配）；比赛节点连向参赛的两支队伍（容量 ∞）；每支队伍 i 连向超级汇 T*，容量 W0 + r0 − Wi。然后求最大流。如果最大流等于剩余比赛的总场数，说明每一场的胜场都能被”安全地”分配，T0 仍有机会；否则，即使其他队伍都输给 T0，也至少有一场的结果会把某支队伍推到 T0 之上，T0 被淘汰。

graph LR
    S["S*"] -->|"1"| M1["甲vs乙"]
    S -->|"1"| M2["甲vs丙"]
    S -->|"1"| M3["乙vs丙"]
    M1 -->|"∞"| A["甲"]
    M1 -->|"∞"| B["乙"]
    M2 -->|"∞"| A
    M2 -->|"∞"| C["丙"]
    M3 -->|"∞"| B
    M3 -->|"∞"| C
    A -->|"上限甲"| T["T*"]
    B -->|"上限乙"| T
    C -->|"上限丙"| T

这个例子把第 2.3 节的”多源多汇”技巧、第 8.1 节的”单位容量”思想和第 7 节的最小割判据全部用上了：剩余比赛数能不能全部消化，等价于”是否存在满流”。类似的建模还出现在电路板测试、会议排程、供应链分配等无数场景里。

8.7 网络流进阶方向一览

本篇到 Edmonds-Karp 为止，已经覆盖了网络流的核心骨架。如果你觉得意犹未尽，下面这些进阶方向可以作为后续学习路线图：

Dinic 算法：每轮 BFS 分层 + DFS 多路增广，复杂度 O(V²·E)，稠密图与竞赛场景的主力。ISAP：在 Dinic 基础上维护距离标号，常数更小。Push-Relabel（预流推进）：换一个视角，让顶点暂时”积水”再推向邻居，理论上更接近最大流本质。最小费用最大流：在”流最大”之外还要求”费用最小”，引入费用函数与最短路/SPFA。上下界网络流：每条边的流量被限定在 [L, U] 区间，需要先判断可行性再求极值。全局最小割（Stoer-Wagner）：不指定源汇，求整个无向图的最小割，与最大流定理互为你中有我。最大权闭合子图：正是 8.3 节项目选择的推广，是”最大流最小割”在决策问题上的标准模板。

这些算法大多建立在今天的两块基石上：残量网络的反向边机制，以及”无增广路径即最大流”的判定。地基打牢了，上面的楼想盖多高都可以。

9 要点速查表

概念	一句话	关键点
流网络	有向图 + 源 S + 汇 T + 容量 c	每条边有非负容量
可行流	满足容量约束与守恒的流量分配	0 ≤ f ≤ c；中间顶点进出相等
流的值	S 的净流出量	等于 T 的净流入量
残量网络	当前流派生的”还能怎么改”图	正向边剩 c−f，反向边剩 f
反向边	撤回流量的记账边	真实状态仍是 f ≥ 0，不超容
增广路径	残量图中 S→T 路径	瓶颈 = 最小残量
增广	沿路径加瓶颈流量	每次使
Ford-Fulkerson	循环”找路—增广—直到无路”	任意选路，可能很慢
Edmonds-Karp	BFS 每次找最短增广路	复杂度 O(V·E²)
最大流最小割定理	最大流 = 最小割容量	任意流 ≤ 任意割
求最小割	最后一次残量 BFS 的可达集	割边 = 从 X 到 Y 的原边
二分图匹配	源连左、右连汇、边容量 1	最大流 = 最大匹配
超级源/超级汇	把多源多汇归约为单源单汇	用容量 +∞ 的边连接
0/1 流	容量全为 1 时的整值流	对应匹配等离散选择

10 自测题（含答案）

11 下一篇预告

恭喜你，走完了网络流最核心的一段旅程。从配水管网的一问，到流网络的四件套，到残量图与反向边的”后悔药”，到 Edmonds-Karp 的 BFS 增广，再到最大流最小割定理这个漂亮的顶峰——你现在拥有的，是组合优化里最有力的建模工具之一。

下一篇《图系列第 15 篇：二分图匹配与综合实战》，我们将把今天埋下的种子浇灌成树：二分图最大匹配的增广路算法、König 定理、最大匹配与最小点覆盖的互相转化，以及一系列综合实战题——用最大流建模、用最小割证明、用匹配算法求解。到那时你会发现，第 14 篇的每一个概念都会在实战中重新发光。

下次见，朋友。记得亲手把 5.3 节的例子跑一遍代码，让理论真正变成肌肉记忆。愿每一滴水都流到它该去的地方。