目录
1. 什么是流网络？
想象一个复杂的城市供水系统。你有一个主水处理厂将水推出，以及一个主水库，所有的水最终都会流向那里。在它们之间是一个由不同大小的管道组成的庞大网络。
有些管道是巨大的主水管（高容量），而另一些是小型住宅管道（低容量）。问题是：在不撑破任何管道的情况下，每秒钟能从水厂泵入水库的最大水量是多少？
在图论中，这被建模为流网络 (Flow Network)。流网络是一个有向图，其中：
- 源点 (Source, s)：“流”起源的起始节点（水厂）。
- 汇点 (Sink, t)：所有“流”最终到达的目的地节点（水库）。
- 边 (Edges)：节点之间的连接（管道）。
- 容量 (Capacity, c)：边可以处理的最大流量（管道的宽度）。
2. 网络流的三个规则
要从数学上定义通过该网络的有效流，我们必须遵循三个绝对规则：
- 容量限制 (Capacity Constraint)：任何边上的流都不能超过其容量。如果一根管道每秒能容纳 10 加仑，你就不能通过它推入 11 加仑。数学上：
0 ≤ f(u,v) ≤ c(u,v)。 - 流量守恒 (Conservation of Flow)：对于图中的每个节点（源点和汇点除外），进入该节点的总流必须完全等于离开该节点的总流。节点不会神奇地产生或消耗水。进多少出多少。
- 斜对称性 (Skew Symmetry, 可选但有用的规则)：从节点 U 到 V 的流是从 V 到 U 的流的相反数。如果 5 个单位从 U 流向 V，那么 -5 个单位从 V 流向 U。
最大流问题 (Maximum Flow Problem) 的目标是找到对每条边的有效流量分配，从而最大化离开源点 s 的总流（由于流量守恒，它将完全等于到达汇点 t 的总流）。
3. Ford-Fulkerson 算法（增广路径）
为了解决最大流问题，我们使用开发于 1956 年的 Ford-Fulkerson 算法。其背后的逻辑非常直观。
该算法的工作原理如下：
- 从所有边上的流为 0 开始。
- 找到一条从源点到汇点的路径，其中路径上的每条边都有可用的、未使用的容量。这被称为增广路径 (Augmenting Path)。
- 在这条路径上找到可用容量最小的边。这就是“瓶颈 (bottleneck)”边。
- 沿着整条路径推送等于瓶颈容量的流。
- 重复步骤 2-4，直到找不到更多增广路径。
当您再也找不到从源点到汇点可以接受更多流的路径时，您就已经找到了最大流。但是等等，这里有一个陷阱！
4. 秘密武器：残量网络
如果你完全按照上面描述的实现 Ford-Fulkerson，你可能会得到错误的答案。为什么？因为你可能在早期做了一个“糟糕”的贪心选择，将流送到了一条管道，而这条管道阻碍了后来更好的路线。
为了解决这个问题，Ford-Fulkerson 利用了一个出色的概念，称为残量网络 (Residual Graph)。残量网络允许算法“撤销”糟糕的决定。
每当你沿着一条边从 U 到 V 向前推送 X 个单位的流时，你必须在残量网络中添加一条从 V 到 U 的容量为 X 的“反向边”。这条反向边代表了你“推回”或取消你刚才发送的流的能力。
如果未来的增广路径利用了这些反向边之一，它实际上是将你之前发送的水重定向到一条不同的、更优的管道。您必须始终在残量网络中搜索增广路径，而不是在原始图中。
5. 最大流最小割定理
这就引出了图论中最美丽、最深刻的定理之一：最大流最小割定理 (Max-Flow Min-Cut Theorem)。
想象一下，你想彻底破坏城市的供水系统。你想切断一组管道，使得绝对没有一滴水能从处理厂到达水库。自然地，你想以最少的努力做到这一点，这意味着你想切断总组合容量尽可能小的管道。
这被称为割 (Cut)。一个 s-t 割将图的节点划分为两个集合：一个包含源点 (s)，另一个包含汇点 (t)。割的容量是从源集合到汇点集合的所有边的容量之和。
最小割 (Minimum Cut) 是总容量可能最小的割。
该定理陈述了一个不可思议的等价关系：
你能通过网络推送的最大流量完全等于最小割的容量。
它们是同一枚硬币的两面。限制你的流的瓶颈正是你要切断网络所针对的同一个瓶颈。通过（使用 Ford-Fulkerson）求解最大流，你同时找到了最小割的精确值。
6. 改进 Ford-Fulkerson：Edmonds-Karp 算法
Ford-Fulkerson 有一个缺陷：它没有告诉你如何找到增广路径。如果你只是使用任意的深度优先搜索 (DFS)，并且你的图有非常特定的边权重，算法的运行速度可能会慢得令人难以置信。事实上，如果边容量是无理数，普通的 Ford-Fulkerson 甚至可能永远不会终止！
在 1972 年，Jack Edmonds 和 Richard Karp 发布了一个简单而绝妙的修改：始终使用广度优先搜索 (BFS) 寻找最短的增广路径。
通过强制算法找到具有最少边数（忽略容量）的增广路径，Edmonds-Karp 算法保证了多项式时间复杂度 O(V * E^2)，完全独立于边上的实际容量值。
7. 现实世界的应用
网络流算法不仅适用于管道工程。它们在软件工程和运筹学中解决令人难以置信的复杂的分配和路由问题。
最大二分图匹配 (Maximum Bipartite Matching)
想象一下，你有 5 名求职者和 5 份可用工作。每个求职者只符合某些工作的资格。你如何将最多的人分配到他们符合条件的工作？
你可以把它变成一个最大流问题！创建一个“源点”节点，并以容量 1 将其连接到所有求职者。将求职者以容量 1 连接到他们符合条件的工作。将所有工作以容量 1 连接到“汇点”节点。运行 Ford-Fulkerson。最大流将完美等于你能成功雇用的最大人数。
计算机视觉中的图像分割
在计算机视觉中，将对象（前景）与其背景分离是一个经典问题。通过将像素表示为一个图，其中边代表相邻像素之间的颜色相似度，将前景从背景中切割出来的问题可以完美映射为最小割 (Minimum-Cut) 问题。
体育淘汰赛 (Sports Elimination)
在一个棒球赛季中，你能在数学上证明一支球队已经被淘汰出季后赛吗，即使他们赢了所有剩下的比赛？通过创建一个代表所有其他球队之间剩余比赛的流网络，你可以使用最大流来证明是否存在该球队仍可能赢得赛区的场景。
常见问题
什么是最大流最小割定理？
该定理指出，在一个流网络中，从源点到汇点的最大流量等于将源点和汇点分离的最小割的边容量之和。
福特-富尔克森 (Ford-Fulkerson) 与 埃德蒙兹-卡普 (Edmonds-Karp) 算法有什么区别？
福特-富尔克森是一个通用的求解方法，可使用 DFS 或 BFS 寻找增广路径，复杂度为 O(E * f)。埃德蒙兹-卡普是其具体实现，强制使用 BFS 搜索，确保了 O(V * E²) 的多项式级时间复杂度。
网络流中的残量图（Residual Graph）是什么？
残量图表示网络中每条边剩余的容量通道。它记录了正向的剩余可用容量以及反向的（可撤销或重新路由的）流量容量。