最大流计算器

伪代码

这一族的所有最大流算法本质上是同一个循环：找出一条从源点到汇点、尚有剩余容量的路径，沿它尽可能多地推送流量，然后重复。它们的差别只在于如何挑选这条路径。

最大流(图, s, t):
    流量 = 0
    构建残量图：正向为 cap(u,v)，反向为 0

    当残量图中仍存在从 s 到 t 的增广路径 P 时:
        瓶颈 = P 上最小的残量容量
        对 P 上的每条边 (u, v):
            残量[u][v] -= 瓶颈
            残量[v][u] += 瓶颈      // 撤销边
        流量 += 瓶颈

    返回 流量

// Ford-Fulkerson：用 DFS 找 P（任意路径）
// Edmonds-Karp：  用 BFS 找 P（最短路径）

那条反向的残量边看上去像是写错了，实际上却不可或缺。它让后来的增广路径能够撤销先前推送的流量，于是算法无需显式回溯就能摆脱早期的错误选择。没有这些撤销边，这个贪心循环会卡在一个并非最优的流量上。

分步示例演算

在那个经典的例子上运行 Edmonds-Karp：其中最初的贪心选择必须在后面被撤销。

示例图: 有向容量：S 到 A (10)、S 到 B (10)、A 到 B (2)、A 到 T (4)、B 到 T (9)。

1. 第 1 次增广. BFS 找到 S 到 A 到 T。瓶颈为 min(10, 4) = 4。推送 4，总流量为 4。残量中 S-A 降为 6，A-T 降为 0。
2. 第 2 次增广. BFS 找到 S 到 B 到 T。瓶颈为 min(10, 9) = 9。推送 9，总流量为 13。残量中 S-B 降为 1，B-T 降为 0。
3. 第 3 次增广. A-T 与 B-T 都已饱和，因此不存在直达路线。BFS 再也找不到增广路径：要抵达 T 就必须经过 A-T 或 B-T，而两者都已满。
4. 检查这个割. 哪些边饱和了？A-T 的 4 与 B-T 的 9，容量合计 13。删掉它们就把 T 与 S 分开，因此这是一个容量为 13 的割，而流量 13 恰好与之相等。
5. 为什么撤销边很关键. 假如第一条增广路径是 S 到 A 到 B 到 T 并推送了 2，那么 A-B 会以一种在此处并不造成阻塞的方式被占满。但在那些贪心路径抢走了后续路径所需容量的图中，反向残量边 B 到 A 就能把这 2 个单位推回去并重新分配。算法始终不需要显式回溯。

最大流为 13，而最小割是边对 A-T 与 B-T，容量合计 13。两个数字相等并非巧合：这就是最大流最小割定理。

复杂度及其来源

时间: 使用 Edmonds-Karp 时为 O(V·E^2) · 空间: O(V + E)

若路径选择是任意的，Ford-Fulkerson 的复杂度为 O(E 乘以最大流量)，因为每次增广至少增加一个单位，而每次寻找路径要花 O(E)。这是伪多项式的，而且确实很糟：当容量达到十亿量级时，它可能需要十亿次增广；若容量为无理数，甚至可能不终止。Edmonds-Karp 通过始终用 BFS 选取最短增广路径解决了这一问题。源点到汇点的距离不会减小，且每条边至多成为瓶颈 V/2 次，这把增广次数限制在 O(VE)，总代价限制在 O(V 乘以 E 的平方)。Dinic 借助层次图把增广分阶段成组处理，进一步改进到 O(V 的平方乘以 E)，在单位容量图上则为 O(E 乘以根号 V)。

何时使用最大流，何时不宜

如何选择，主要取决于容量的数量级与图的规模。

常见陷阱

• 漏掉反向残量边. 没有它们，算法就无法撤销先前的糟糕增广，最终停在一个仅仅「无法再扩充」而非数值最大的流上。这是最大流最常见的错误，它给出的答案看似合理却偏小。
• 容量很大时仍用 DFS 选路径. 在不利的图上，纯 Ford-Fulkerson 配合 DFS 可能每推送一个单位就需要一次增广。经典例子中容量为一百万、瓶颈边为一，就需要一百万次迭代。改用 BFS 后，增广次数与容量数值无关。
• 忘记流量守恒不包括源点和汇点. 除源汇之外的每个结点都必须入流等于出流。在源点或汇点上校验守恒必然失败，这在编写测试时是常见的困惑来源。
• 以为最大流唯一. 最大流的数值是唯一的，但达成它的具体流量分配通常不唯一；当多个割容量相同时，最小割也不唯一。测试应当检查数值，而不是逐边的分配方案。
• 把结点容量当作边容量来建模. 若某个结点自身有吞吐上限，必须把它拆成入点与出点，并用一条该容量的边相连。把限制施加到相邻边上，得到的是另一个而且错误的问题。

常见问题

什么是最大流问题？

给定一个每条边都带容量的有向图，以及一个源点和一个汇点，最大流问题求的是物资从源点流向汇点的最大速率，且不得超过任何一条边的容量，同时在每个中间结点保持流量守恒。它可用来刻画管道、网络、物流与调度中的吞吐能力。

什么是最大流最小割定理？

从源点到汇点的最大流量总是等于分离二者的最小割的容量。直观地说，流量无法超过任何一个割，因为一切都必须跨过它；而当不再存在增广路径时，残量图中可达的结点恰好定义出一个割，其容量正好被该流量达到。

Ford-Fulkerson 与 Edmonds-Karp 有什么区别？

两者是同一种增广路径方法，只是选路方式不同。Ford-Fulkerson 未规定如何选路，通常用 DFS，这使运行时间依赖于容量数值，可能慢得离谱。Edmonds-Karp 始终用 BFS 选取最短增广路径，从而把工作量限制在 O(V 乘以 E 的平方)，与容量数值无关。

最大流算法为什么需要残量边？

因为算法是贪心的，无法预见未来。反向残量边代表「撤销此前沿该边推送的流量」这一选项，使后来的增广路径能够改变先前的决策。正是这一点让一个只会向前推进的循环无需回溯就能达到真正的最优。

最大流的时间复杂度是多少？

Edmonds-Karp 为 O(V 乘以 E 的平方)。Dinic 改进到 O(V 的平方乘以 E)，在单位容量图上为 O(E 乘以根号 V)，这也是二分图匹配偏爱它的原因。纯 Ford-Fulkerson 为 O(E 乘以最大流数值)，属于伪多项式而非多项式。