★ FEATURED ARTICLE 1. 从水管网络说起最大流到底在解决什么问题很多人第一次接触网络流看到源点汇点增广路残量网络这一串术语就头大觉得这是竞赛里才用的高深算法。其实把场景换一下它朴素得不能再朴素。想象你所在的小区有一套供水管网。水从自来水厂源点出发经过一级一级的管道、阀门、中转站最终送到你家楼顶的水箱汇点。每根管道都有粗细单位时间内能通过的水量有上限。现在问从水厂到水箱单位时间内最多能送多少水这就是最大流问题。把水换成货物数据包车辆电流把管道换成公路网线电路问题本质完全一样。所以最大流是运筹学和图论里最经典的模型之一物流调度、任务分配、图像分割、二分图匹配背后都能看到它的影子。我写这篇东西的出发点很直接网上讲最大流的文章要么一上来就是定理证明要么代码贴完就没了中间为什么这么写这个变量到底代表什么全靠自己悟。我当年入门的时候对着一段 Dinic 代码盯了一下午才想明白level数组和iter数组各自在干嘛。所以这里我打算把 FF、EK、Dinic、ISAP 四个算法从最朴素的思路一路推到能直接抄的模板重点讲清楚每一步的动机而不是只给结论。适合谁看如果你刚学完图的存储邻接表、链式前向星知道 BFS 和 DFS 怎么写那这篇就是为你准备的。如果你已经会 Dinic也可以看看 ISAP 的 gap 优化和当前弧优化那几段那是我踩过坑的地方。先约定几个基础概念后面全程用这套记号容量cap(u, v)边 u→v 单位时间能通过的最大流量。流量flow(u, v)实际通过的流量必须满足0 ≤ flow(u, v) ≤ cap(u, v)。流量守恒除了源点 s 和汇点 t任何中间节点流入总量等于流出总量。水不会在中转站凭空消失或产生。可行流满足容量限制和流量守恒的一组 flow。最大流所有可行流里从 s 流出的净流量最大的那个值。注意网络流里流量是个瞬时速率的概念不是累计总量。你可以理解成每秒多少立方米这样后面讲增广的时候不会绕晕。2. 增广路思想FF 算法为什么能跑但很慢2.1 残量网络给反悔留一条后路最大流所有算法的地基都是同一个东西——残量网络residual network。这个概念不理解后面全是死记硬背。对每条边 u→v我们定义它的残量res(u, v) cap(u, v) - flow(u, v)也就是这条边还能再塞多少流量。同时我们人为地加一条反向边 v→u它的残量等于正向边已经流过的量flow(u, v)。反向边是干嘛的它是反悔通道。假设你一开始把 5 个单位的水从 A 送到了 B后来发现这条路走错了应该从 A 送到 C。如果没有反向边你没法把已经送出去的水收回来。有了反向边 B→A残量为 5你就可以从 B 沿着这条反向边把 5 个单位退回 A再改道去 C。反向边不是真实存在的管道它是一个记账工具让算法具备撤销能力。这一点极其关键。很多人写代码时忘了反向边容量初始为 0或者更新时只更新正向不更新反向结果算法要么死循环要么答案偏小。2.2 Ford-Fulkerson 的朴素循环FF 算法的思路简单到粗暴在残量网络里找一条从 s 到 t 的路径要求路径上每条边的残量都大于 0。这条路径叫增广路。找出这条路径上残量最小的那条边设这个值为bottleneck。沿着路径每条正向边流量加bottleneck每条反向边流量减bottleneck等价于正向边残量减、反向边残量加。重复 1-3直到找不到增广路为止。为什么找不到增广路就是最大流这是最大流最小割定理的内容一个流是最大流当且仅当残量网络中不存在 s 到 t 的路径。割的概念这里先不展开你只要记住这个判定条件就行。FF 的问题在于第 1 步找一条路径没有规定怎么找。如果每次随便找遇到某些构造数据每次只增广 1 个单位而最大流是很大的数算法就会退化成增广值 × 路径长度的复杂度慢到无法接受。经典的例子是中间有一条容量为 1 的边两边是容量为 10^9 的边随机找路径可能来回横跳几亿次。2.3 一个具体的反例感受一下构造这样一个图s→a 容量 1000000s→b 容量 1000000a→b 容量 1a→t 容量 1000000b→t 容量 1000000。如果第一次增广走了 s→a→b→tbottleneck 是 1被 a→b 卡住。第二次如果又走了 s→b→a→t借助反向边 b→abottleneck 还是 1。这样每次只能增广 1要增广两百万次才能到最大流。这就是 FF 在路径选择上的致命缺陷。所以 FF 本身更多是理论意义实际写代码没人用它。但它引出了下一个改进方向既然随便找会出问题那我固定一种找法比如每次找边数最少的那条增广路行不行这就是 EK 算法。3. EK 算法用 BFS 把增广路最短化3.1 为什么选边数最少的增广路Edmonds-Karp 算法的核心改动只有一句话每次用 BFS 找增广路找的是经过边数最少的那条。为什么这样就能把复杂度压下来直觉上边数最少的增广路意味着绕路最少每次增广后源点到各点的最短距离按边数算不会减少而且每增广一次至少有一条边会被用满从而在残量网络里消失这条边对应的距离会单调增加。严格证明涉及势能分析结论是EK 的增广次数上界是 O(VE)每次 BFS 是 O(E)总复杂度 O(VE²)。对于点数几百、边数千把的图这个复杂度完全够用。而且 EK 的代码非常好写是理解后续算法的绝佳跳板。3.2 EK 的完整流程拆解我用链式前向星存图每条边存to终点、cap当前残量、next下一条边。加边的时候成对加正向边残量设为容量反向边残量设为 0两条边通过下标异或 1 互相找到对方i ^ 1。struct Edge { int to, next, cap; } e[MAXM]; int head[MAXN], cnt 0; void addEdge(int u, int v, int c) { e[cnt] {v, head[u], c}; head[u] cnt; e[cnt] {u, head[v], 0}; head[v] cnt; }BFS 部分要记录两个东西preEdge[v]表示到达 v 的那条边的下标preNode[v]表示 v 的前驱节点。找到汇点后从 t 往回走沿路取最小残量作为 bottleneck然后再走一遍更新残量。bool bfs(int s, int t) { memset(vis, 0, sizeof(vis)); queueint q; q.push(s); vis[s] 1; while (!q.empty()) { int u q.front(); q.pop(); for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; if (!vis[v] e[i].cap 0) { vis[v] 1; preNode[v] u; preEdge[v] i; if (v t) return true; q.push(v); } } } return false; }主循环里反复 BFS每次增广累加流量。3.3 我踩过的两个坑第一个坑反向边容量更新方向搞反。正向边e[i].cap - bottleneck反向边e[i^1].cap bottleneck。我一开始写成反向边也减结果残量网络直接崩了答案偏小还查不出原因。记住正向减、反向加因为反向边代表可撤销的量撤销的量越多反向残量越大。第二个坑BFS 里判断cap 0而不是cap 0。残量为 0 的边是不能走的必须严格大于 0。这个细节在 EK 里不明显但到了 Dinic 的 DFS 里如果写成 0会陷入死循环。提示EK 每次只增广一条路效率一般。但它的正确性最容易验证建议先用 EK 写一版暴力后面用 Dinic 写一版两版对拍能快速定位 bug。4. Dinic 算法分层图 当前弧一次 BFS 多次增广4.1 分层图把能走的边限制在同一层EK 的浪费在于每次 BFS 只为了找一条增广路找到就重来。Dinic 的想法是BFS 一次把整个图按到源点的距离分层然后只允许沿着层数 1的方向走。这样一次 BFS 之后可以连续做多次 DFS 增广直到这个分层图上再也找不到增广路再重新 BFS 分层。level[v]就是 v 到源点的最短边数。BFS 时只从level[u]能推到level[v] level[u] 1的边。DFS 增广时也只走满足level[v] level[u] 1的边。为什么这样能加速因为分层图是一个 DAG有向无环图沿着层数递增走不可能绕回来DFS 不会打转。而且一次分层能榨干所有最短路径上的增广潜力。4.2 当前弧优化别重复扫已经废掉的边这是 Dinic 的灵魂优化也是最多人写错的地方。iter[u]记录的是对于节点 u从哪条边开始还没试过。DFS 的时候如果某条边已经增广完了残量为 0或者它指向的点已经无法再往汇点送流那下次再访问 u 时就没必要从头再扫一遍这些废边。int dfs(int u, int t, int f) { if (u t) return f; for (int i iter[u]; i ! -1; i e[i].next) { int v e[i].to; if (e[i].cap 0 level[v] level[u] 1) { int d dfs(v, t, min(f, e[i].cap)); if (d 0) { e[i].cap - d; e[i ^ 1].cap d; return d; } } } return 0; }注意for (int i iter[u]; ...)这里用了引用i的递增会直接写回iter[u]。如果写成普通变量当前弧优化就失效了复杂度会退化。这个坑我见过太多人中招。4.3 Dinic 的复杂度与适用边界Dinic 的复杂度是 O(V²E)。看起来和 EK 差不多别急对于单位容量图每条边容量都是 1Dinic 的复杂度是 O(E√V)这是它最漂亮的性质也是二分图匹配能用 Dinic 高效求解的原因。对于一般图实际运行速度远好于理论上界绝大多数竞赛题都能过。主循环长这样int dinic(int s, int t) { int flow 0; while (bfs(s, t)) { for (int i 1; i n; i) iter[i] head[i]; int f; while ((f dfs(s, t, INF)) 0) flow f; } return flow; }每次 BFS 重建 level重置 iter然后 DFS 反复增广直到增不动。4.4 一个容易忽略的细节INF 的取值DFS 入口传的f是INF表示从源点出发理论上能送无限多。这个 INF 要大于所有边容量之和否则会截断。一般取0x3f3f3f3f或者1e9就够。但如果你的容量本身就有 1e9 级别记得开大一点或者用long long。我吃过一次亏容量是 2e9INF 设了 1e9结果答案永远卡在 1e9调了半天才发现是 INF 太小。5. ISAP 算法一次 BFS 分层靠 gap 优化提前收工5.1 ISAP 和 Dinic 的本质区别ISAPImproved Shortest Augmenting Path的思路和 Dinic 很像都用分层和当前弧但有一个关键差异Dinic 每次增广完要重新 BFS 分层ISAP 只在最开始 BFS 一次之后靠距离标号的动态调整来维持分层信息。ISAP 里dep[v]表示 v 到汇点 t 的距离注意方向是到汇点不是到源点。初始时用一次从 t 出发的 BFS 求出所有点的 dep。增广时只走dep[v] dep[u] - 1的边因为 dep 是到汇点的距离往汇点走距离应该递减。当某个点 u 的所有出边都增广完了找不到能往汇点送流的边就把dep[u]加 1让它降级重新有机会被其他路径使用。如果dep[s] n说明源点已经和汇点断开了算法结束。5.2 gap 优化为什么它能大幅提速gap 优化的核心观察是如果某个距离值 k 对应的节点数量变成 0那么所有 dep 大于 k 的节点都不可能再到达汇点了。为什么因为从源点到汇点的路径dep 值必须连续递减每次减 1。如果中间某个 dep 值 k 没有任何节点那路径就断了源点无法到达汇点。这时候可以直接结束算法。实现上用一个gap[]数组统计每个 dep 值的节点数量。初始 BFS 后统计一遍。当某个点 u 的 dep 从 d 变成 d1 时gap[d]--gap[d1]。如果gap[d] 0说明距离 d 断档了直接终止。这个优化在稠密图或者特殊构造图上效果拔群能把运行时间砍掉一大截。我实测过一个 5000 点、50000 边的图不加 gap 优化跑了 1.2 秒加了之后 0.3 秒。5.3 ISAP 的 DFS 写法与当前弧ISAP 的 DFS 通常写成一次推一点的形式配合当前弧int dfs(int u, int t, int f) { if (u t) return f; int used 0; for (int i cur[u]; i ! -1; i e[i].next) { int v e[i].to; if (e[i].cap 0 dep[u] dep[v] 1) { int d dfs(v, t, min(f - used, e[i].cap)); if (d 0) { e[i].cap - d; e[i ^ 1].cap d; used d; if (used f) return used; } } } // 所有出边都试完了还没送满降级 if (--gap[dep[u]] 0) dep[s] n; // 断档终止 dep[u]; gap[dep[u]]; return used; }这里used变量很关键它保证一次 DFS 尽量把 f 送满而不是送一点就返回。这样能减少递归次数。5.4 ISAP 的初始化 BFS 方向别搞反ISAP 的初始 BFS 是从汇点 t出发沿反向边残量大于 0 的边BFS求每个点到 t 的距离。很多人习惯性从源点 BFS结果 dep 全错算法要么死循环要么答案错。void bfs(int t) { memset(dep, -1, sizeof(dep)); memset(gap, 0, sizeof(gap)); queueint q; q.push(t); dep[t] 0; while (!q.empty()) { int u q.front(); q.pop(); gap[dep[u]]; for (int i head[u]; i ! -1; i e[i].next) { int v e[i].to; if (dep[v] -1 e[i ^ 1].cap 0) { // 注意是反向边残量 dep[v] dep[u] 1; q.push(v); } } } }注意e[i ^ 1].cap 0这个条件。因为是从 t 往回 BFS能走的边是正向边有残量的反向视角所以判断的是反向边残量。这个细节我第一次写的时候也搞混了。6. 四个算法的横向对比与选型建议6.1 复杂度与实测表现对照算法核心思想理论复杂度适用场景代码难度FF任意增广路O(E × maxFlow)理论教学低EKBFS 找最短增广路O(VE²)小图、对拍验证低Dinic分层图 当前弧O(V²E)单位容量 O(E√V)通用首选中ISAP距离标号 gap 优化与 Dinic 同阶常数更优稠密图、卡常场景中高从实战角度我的建议是默认写 Dinic卡常了再上 ISAP。Dinic 的代码结构清晰调试方便90% 的题目都能过。ISAP 虽然快但 gap 优化和 dep 调整的逻辑稍微绕一点写错了不容易发现。6.2 什么时候该考虑 ISAP三种情况我会优先用 ISAP图的点数超过 1e4边数超过 1e5Dinic 可能 TLE。题目明确卡常数或者时间限制很紧。图比较稠密分层图重建开销大ISAP 一次 BFS 的优势明显。反过来如果图很小几百个点Dinic 和 ISAP 的差距可以忽略选你写得更熟的那个就行。6.3 关于 long long 的取舍如果边容量可能超过 2^31必须用long long。但long long的运算比int慢如果容量都在 int 范围内别为了保险全开 long long会白白损失性能。我的习惯是先看题目数据范围容量和最大流之和不超过 2e9 就用 int否则 long long。7. 实战中的高频坑与调试技巧7.1 数组开小了导致 RE 或 WA链式前向星里每条无向边要存成两条有向边所以边数组大小是2 * M。如果题目给 M 条边你开M大小加边的时候就越界了。我一般直接开2 * M 10留点余量。点数同理如果题目节点编号从 1 开始数组开到N 10。别省这点空间。7.2 多组数据忘记清空竞赛题经常有多组测试数据。每次跑之前head数组要重置为 -1cnt要归零。如果用了dep、gap、iter这些数组也要在对应位置清空。我见过有人只清了 head 忘了 cnt结果第二组数据加边从错误的下标开始直接崩盘。7.3 源点和汇点的编号有些题目源点和汇点不是 1 和 n而是额外指定的。读题时一定看清楚。还有的题目有多个源点或多个汇点这时候要建一个超级源点连向所有源点容量无穷大再建一个超级汇点所有汇点连向它。这个技巧在任务分配类题目里很常见。7.4 用对拍验证正确性我的标准流程是先写一版 EK慢但稳再写一版 Dinic然后随机生成小规模图点数 10 以内边数 20 以内容量 10 以内跑几百组对拍。两版答案一致才说明 Dinic 写对了。这个习惯帮我省了无数调试时间。7.5 关于递归深度Dinic 和 ISAP 的 DFS 是递归的如果图是一条长链递归深度可能达到点数。点数上万时某些环境可能爆栈。解决办法是把递归改成显式栈的迭代版本或者调大栈空间。竞赛里一般不用担心但工程环境要注意。8. 从最大流延伸出去这些变体你迟早会遇到最大流本身是个工具真正有意思的是它的变体。这里提几个入门后必然会碰到的方向算是给你指条路。最小费用最大流在每条边上加一个单位流量费用要求在流量最大的前提下总费用最小。求解思路是把 BFS 找增广路换成 SPFA 或 Dijkstra 找费用最小的增广路。这是最大流最常用的扩展物流调度、任务分配带成本的问题都靠它。二分图最大匹配把左部点连源点、右部点连汇点所有边容量设为 1跑最大流最大流值就是最大匹配数。因为单位容量图 Dinic 是 O(E√V)所以这是二分图匹配的高效解法。最小割根据最大流最小割定理最大流的值等于最小割的容量。很多删掉最少的边使图不连通选择最少的代价切断某些联系的问题本质都是最小割直接跑最大流即可。上下界网络流每条边除了容量上限还有下限要求流量在 [low, high] 之间。这个稍微复杂需要先做一次可行流转化再跑最大流。入门阶段可以先跳过等把基础最大流写熟了再回头看。我个人的学习路径是先把 Dinic 写到闭着眼睛能默写然后用它去刷二分图匹配的题再过渡到最小费用最大流。每一步都建立在上一版代码能跑对的基础上不要跳步。最大流这东西看懂和写对之间隔着一条河只有自己一行行敲出来、调出来那些坑才会真正变成你的经验。最后分享一个我常用的调试手段在增广的时候打印每次的路径和 bottleneck观察增广过程是否符合预期。如果发现某条边反复被增广又撤销说明你的分层或当前弧有问题。这个笨办法在初学阶段比任何理论分析都管用。
阅读完成 · 觉得有帮助？
