type
Post
status
Published
date
May 4, 2026
slug
maxflow
summary
tags
算法
category
icon
password
一、 问题背景：从自来水管网说起
想象你是一座城市的自来水公司经理。城市里有一个巨大的水库（负责不断供水），还有一个居民区（负责不断用水）。水库和居民区之间，由无数条粗细不一的水管交织相连。
每根水管都有它的“极限”，比如某根细管子每秒最多只能流过 3 吨水，这叫作这根管子的容量。
现在你要解决的核心问题是：在所有的水管都不爆裂（不超载）的前提下，水库每秒钟最多能给居民区输送多少吨水？
这就是图论中经典的最大流问题（Maximum Flow）。
二、 算法原理：三个核心大白话
在正式介绍算法前，我们先统一几个通俗的称呼（括号里是专业的图论术语）：
- 起点（源点 Source，简称 S）：只出水、不进水的水库。
- 终点（汇点 Sink，简称 T）：只进水、不出水的居民区。
- 管道粗细（容量 Capacity）：这条路最多能承受的流量。
- 实际水流（流量 Flow）：当前这条路上实际流了多少水。显然，实际水流不能超过管道粗细。
求解最大流最基础的思想叫 Ford-Fulkerson 方法。它的原理非常直白：只要还能找到一条从起点到终点的通水路径，就往死里灌水，直到再也找不到任何一条能通水的路为止。
三、 核心思路：找路与“后悔药”
具体怎么找路？这里有两个极其重要的概念，是整个最大流算法的灵魂。
1. 见缝插针：增广路（Augmenting Path）
“增广路”听起来很吓人，说白了就是一条还没被装满、还能继续流水到底的路径。
比如从起点到终点有一条路：A -> B -> C。
- A 到 B 的管子还能再容纳 5 吨水。
- B 到 C 的管子还能再容纳 2 吨水。 那么这条路作为整体，最多只能再额外通过 2 吨水（受限于最窄的瓶颈——木桶效应）。我们把这额外的 2 吨水顺着这条路流过去，总流量就增加了 2 吨。寻找这条路的过程，就叫“寻找增广路”。
2. 核心灵魂：反向边（“后悔药”机制）
如果只是单纯地找路灌水，会遇到一个致命问题：贪心导致的短视。
假设有这样一个网络：
- 水库 S 到 中转站 A，容量为 10
- 水库 S 到 中转站 B，容量为 10
- 中转站 A 到 中转站 B，容量为 1 （这是一条极窄的岔路）
- 中转站 A 到 居民区 T，容量为 10
- 中转站 B 到 居民区 T，容量为 10
如果计算机很笨，第一次找路时瞎走，找到了
S -> A -> B -> T，因为中间那条路容量只有 1，所以这条路只能流过 1 吨水。
流完之后，A 到 B 的路被堵死了。接着计算机再找路，走 S -> A -> T（流了 9 吨，因为 A 的入口只剩 9 吨空间），走 S -> B -> T（流了 9 吨）。最终总流量是 1 + 9 + 9 = 19 吨。但这不对！聪明的你一眼就能看出，如果不走中间那条
A -> B 的岔路，直接走 S -> A -> T（10吨）和 S -> B -> T（10吨），最大流应该是 20 吨！怎么让计算机“撤销”之前的错误决定呢？ 天才的科学家引入了反向边（Residual Edge）。
规则是：正向水管每流过 $X$ 吨水，就在反方向建立一条容量为 $X$ 的虚拟水管。
结合刚才的例子：
当计算机瞎走了
S -> A -> B -> T 灌了 1 吨水后，系统会自动生成一条 B -> A 容量为 1 的反向虚拟水管。
下一次找路时，计算机可以走 S -> B -> A -> T！- 它从 S 到了 B。
- 顺着虚拟水管从 B “逆流”回到了 A（利用了反向边）。
- 从 A 到了 T。 这步操作在现实生活中的物理意义是：把原本从 A 流向 B 的那 1 吨水给“顶”了回去，让 A 的水直接去 T，让 B 的水自己去 T。 有了反向边，算法就有了“后悔”的能力，怎么瞎走都不怕，最终一定能算出正确答案！
四、 执行步骤：Dinic 算法流程
理解了增广路和反向边，我们就可以直接学习 ACM 竞赛中最常用的最大流算法：Dinic 算法。它不仅聪明，而且速度极快。
Dinic 算法巧妙在它给节点**“分层”**了。水总是往低处流的，为了防止找路时在图里面绕圈子，Dinic 会先用广度优先搜索（BFS）给每个节点标记一个“距离起点的步数”（也就是层数）。
执行步骤拆解：
- 分层（BFS 搜索）：从起点 S 出发，像水波纹一样一层层扩散，给每个能到达的点打上层数标记（距离起点几步）。如果水波纹无法到达终点 T，说明图已经被榨干了，算法结束。
- 找路（DFS 搜索）：从起点 S 出发，沿着层数 严格递增 的方向（比如必须从第 1 层走向第 2 层，不能平流也不能倒流）寻找增广路。
- 榨干（多路增广）：找到一条路后，不要马上退回起点。只要当前节点还有剩余水流，就继续尝试往别的分支流，一次性把一条流水线上能流的水全部榨干。
- 更新图与“后悔药”：流过水后，正向管子容量减少，反向管子（后悔药）容量增加。
- 循环：回到第 1 步重新分层，直到 BFS 无法到达终点。
五、 举小例子手动推演
我们就用刚才那个容易走错的图：S, A, B, T 四个点。
初始容量：
S->A(10), S->B(10), A->B(1), A->T(10), B->T(10)。第一轮分层与灌水：
- BFS 分层：S 是第 0 层。A 和 B 距离 S 一步，是第 1 层。T 是第 2 层。
- DFS 找路：
- 寻路只能向下一层走。因此 A 只能走向 T（A和B都是第1层，不能同层互走，这直接避免了走 A->B 这种窄路！这就是 Dinic 分层的聪明之处）。
- 找到
S -> A -> T，瓶颈是 10。灌入 10 吨水。正向容量减 10 变为 0，反向边容量加 10。 - 找到
S -> B -> T，瓶颈是 10。灌入 10 吨水。
- 第一轮结束，总流量 20。
第二轮分层与灌水：
- BFS 分层：S 的管子都满了（剩余容量为0），水波纹无法扩散，到达不了 T。
- 算法结束：得出最大流为 20。
(注：即使遇到更复杂的图，分层无法完全避开错误路径，反向边的“退流”机制也会在 DFS 阶段完美纠错。)
六、 完整代码与逐行解读（C++ 版）
下面是 Dinic 算法的标准模板代码。我们使用了“前向星”来存图，利用异或操作
^1 可以极快地找到反向边（因为边是从 0, 1, 2, 3 成对存储的，0的异或1是1，1的异或1是0）。七、 优缺点及复杂度
- 优点：
- 通过 BFS 分层严格限制了搜索方向，极大减少了走盲道和绕圈子的情况。
- 当前弧优化（代码中的
ptr数组）：如果一个点连接的一条路被证明不通，同一次 DFS 中再经过这个点时直接跳过这条路，大幅提升效率。
- 缺点：
- 相较于纯天然的 DFS 或 BFS 算法，理解“反向边退流”机制需要跨越思维障碍。
- 时间复杂度：
- 对于一般网络，Dinic 的复杂度上界是 $O(V^2E)$（$V$ 是节点数，$E$ 是边数）。
- 在求解二分图最大匹配时，它的复杂度更是能达到极为优秀的 $O(E\sqrt{V})$，因此在打 ACM 比赛时，绝大多数选手都是无脑敲 Dinic。
八、 适用场景：除了通水，还能干嘛？
最大流算法的魔力在于“抽象”。只要你能把问题转化为“容量”和“流”，就可以用它来秒杀：
- 二分图匹配（相亲问题）：左边一群男生，右边一群女生，连线代表互有好感。把起点连向所有男生（容量1），所有女生连向终点（容量1），求最大流就是最多能成几对！
- 交通疏导 / 网络带宽分配：本质就是图中的水管模型。
- 多源多汇问题：比如多个工厂向多个仓库发货。只要新建一个“超级总水库”连向所有工厂，“超级总居民区”连接所有仓库，就能化归为标准的单源单汇最大流。
- 项目调度 / 任务分配：利用最大流的衍生理图（最小割）来规划成本最低的调度方案。
- 作者:wzy
- 链接:https://wzyblogs.us.ci//article/maxflow
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
