Dinic最大流算法详解：分层图、多路增广与当前弧优化

网络流这个问题，我在刚接触算法竞赛那会儿被它折磨得不轻。当时看到"最大流"三个字觉得挺直观——不就是让水从源点流到汇点，管子粗细有限，问最多能流多少嘛。真上手写代码才发现，里面的门道比想象中多得多。今天就把我这些年反复踩坑、反复重构后沉淀下来的 Dinic 算法实现思路，完整地摊开讲一遍。不管你是刚学完图论基础、准备啃网络流这块硬骨头的算法新手，还是写过 EK 算法但被卡了常数、想升级到 Dinic 的老手，这篇内容应该都能让你少走一些弯路。

1. 最大流问题到底在解决什么

1.1 从一个生活场景理解最大流

先别急着看公式。想象你是一个物流调度员，手头有一张运输网络图：货物从仓库（源点 S）出发，经过若干个中转站，最终要送到门店（汇点 T）。每两个节点之间的运输通道都有固定的日承载上限，也就是容量。你的任务是在不超载任何一条通道的前提下，让从仓库发出的货物总量尽可能大。

这就是最大流问题的本质。把它抽象成图论语言：给定一个有向图，每条边有一个非负容量 cap，指定源点 S 和汇点 T，求从 S 到 T 的最大可行流量。所谓"可行"，要同时满足两个约束——容量限制（每条边的实际流量不超过它的容量）和流量守恒（除了源点和汇点，每个中间节点的流入总量等于流出总量）。

流量守恒这条约束特别关键，很多人一开始会忽略它。你可以这样理解：中转站不囤货，进来多少就得出去多少，不能凭空多出来也不能凭空消失。源点相当于无限供货，汇点相当于无限收货，只有这两个点允许"收支不平衡"。

1.2 为什么不能贪心直接流

新手最容易犯的错误就是：找到一条从 S 到 T 的路径，能流多少流多少，然后重复这个过程直到找不到路径。这个思路叫"贪心增广"，问题在于它可能做出错误的决策。

举个经典的反例。假设 S 到 A 容量 1，S 到 B 容量 1，A 到 B 容量 1，A 到 T 容量 1，B 到 T 容量 1。如果你第一次选的路径是 S→A→B→T，把 A→B 这条边占满了，那么后续 S→A→T 和 S→B→T 都没法走通，最终流量只有 1。但最优解显然是 S→A→T 和 S→B→T 各走 1，总流量为 2。

问题的根源在于：贪心一旦占了某条边，就没有"反悔"的机制。而最大流算法的精髓，恰恰在于引入了反向边，让流量可以"撤销"。当你沿着 A→B 推了 1 单位流量后，同时建立一条 B→A 容量为 1 的反向边。后续如果发现走错了，就可以沿着这条反向边把流量"退回去"，相当于撤销之前的决策。这个反向边的设计，是理解所有最大流算法的钥匙。

1.3 增广路与残量网络

有了反向边的概念，就可以引出两个核心定义。残量网络是指：对于每条原图中的边，正向剩余容量 = 容量 - 当前流量，反向剩余容量 = 当前流量。所有剩余容量大于 0 的边构成的图，就是残量网络。增广路则是在残量网络中从 S 到 T 的一条路径，这条路径上所有边的剩余容量都大于 0，因此可以再推送流量。

最大流定理告诉我们：当残量网络中不存在从 S 到 T 的增广路时，当前流就是最大流。这个定理是整个算法体系的理论基石。所以所有最大流算法的框架都一样——不断在残量网络中找增广路，沿路推送流量，直到找不到为止。不同算法的区别只在于"怎么找增广路"。

EK 算法用 BFS 每次找一条增广路，时间复杂度 O(VE²)，在稠密图上表现一般。而 Dinic 算法通过引入分层图和当前弧优化，把复杂度降到了 O(V²E)，在绝大多数实际场景下跑得飞快。这就是为什么 Dinic 成为了竞赛和工程中最常用的最大流算法。

2. Dinic 算法的核心设计思路

2.1 分层图：给 BFS 加上"只走短路径"的约束

Dinic 的第一步是 BFS 分层。从源点 S 出发做一次 BFS，给每个节点标上一个"层号" level，表示从 S 到该点最少经过几条边。BFS 结束后，如果汇点 T 没有被访问到，说明残量网络中已经没有增广路了，算法结束。

分层图的作用是什么？它强制 DFS 只能沿着 level 递增的方向走，也就是 level[v] = level[u] + 1 的边才允许通过。这样做的好处是：每次 DFS 找到的增广路都是当前残量网络中最短的路径之一。为什么强调"最短"？因为最短增广路的长度在算法执行过程中是单调不减的，这个性质保证了 Dinic 的复杂度上界。

我打个比方帮你理解。假设你在一个陌生城市找路，BFS 分层相当于先算出每个路口距离起点的最少步数，然后你只允许自己走"步数严格加一"的路。这样你走的每一条路都是当前最短的，不会绕远。当所有最短路径都被走完（被流量占满）后，再重新 BFS 分层，寻找下一批更长的路径。

2.2 多路增广：一次 DFS 榨干所有可行路径

EK 算法每次 BFS 只找一条增广路，效率低。Dinic 的改进在于：一次 BFS 分层后，用 DFS 反复寻找增广路，直到当前分层图中再也找不到为止。这就是"多路增广"。

具体来说，DFS 从 S 出发，沿着 level 递增的边往下走，到达 T 就推送流量并回溯。回溯时，如果某个节点的所有出边都已经无法再推送流量（剩余容量为 0 或者指向的节点层号不对），就把它标记为"废弃"，后续不再访问。这样一轮 DFS 可以找出多条增广路，充分利用了这次分层的信息。

这里有个细节值得说：DFS 推送流量时，返回值是"本次能推送的流量"。如果某条边推送后还有剩余容量，说明它可能还能继续推送，但当前 DFS 分支已经走到头了。这时候不需要立刻重试，因为当前弧优化会处理这个问题。

2.3 当前弧优化：避免重复扫描废边

这是 Dinic 最容易被忽略、但对性能影响巨大的优化。在 DFS 过程中，一个节点可能有多条出边。如果第一条出边已经流满了，下次再 DFS 到这个节点时，不应该从头再扫描这条边，而是直接从上次停下的位置继续。

实现方式是用一个数组 cur[u] 记录节点 u 当前正在尝试的边。每次 DFS 到 u 时，从 cur[u] 开始遍历，而不是从 head[u] 开始。当某条边被确认无法再推送流量时，cur[u] 就往后移动一位。这样每条边在每一轮分层中最多被有效访问一次，把 DFS 的复杂度从 O(VE) 降到了 O(E)。

没有当前弧优化的 Dinic，在稠密图上会退化得很难看。我早期写过一个没加这个优化的版本，在一张 500 个点、上万条边的图上跑了将近 10 秒，加上当前弧优化后直接降到 0.1 秒以内。这个差距不是一点半点。

2.4 三种优化的协同关系

把这三个机制串起来看：BFS 分层决定了"哪些边可以走"，多路增广决定了"一次分层能找多少条路"，当前弧优化决定了"找路的过程有多快"。三者缺一不可。

如果只有分层没有多路增广，那就退化成每次 BFS 只找一条路的 EK 算法。如果有多路增广但没有当前弧优化，DFS 会反复扫描已经废弃的边，复杂度爆炸。如果只有当前弧优化没有分层，DFS 可能陷入环里出不来。所以这三个机制是一个整体，写代码的时候一个都不能少。

3. 完整实现与关键代码拆解

3.1 边的存储结构设计

网络流代码里，边的存储方式直接决定了后续操作的便利性。我推荐用邻接表 + 成对存储的方式：每条边存正向和反向两条，它们在数组中的下标满足 i 和 i^1 的关系（即 i 异或 1 得到配对边的下标）。

struct Edge { int to; // 目标节点 int cap; // 剩余容量 int next; // 下一条边的下标 } edge[MAXM * 2]; // 每条边存正反两条，所以开两倍 int head[MAXN], cnt = 0; void addEdge(int u, int v, int cap) { edge[cnt] = {v, cap, head[u]}; head[u] = cnt++; edge[cnt] = {u, 0, head[v]}; // 反向边初始容量为 0 head[v] = cnt++; }

为什么用 i^1 而不是 i+1 或 i-1？因为异或运算不需要判断奇偶，无论 i 是奇数还是偶数，i^1 都能正确得到配对边的下标。如果正边下标是偶数 2k，反边就是 2k+1；如果正边是奇数 2k+1，反边就是 2k。这个技巧在竞赛代码里非常常见，能省掉不少 if 判断。

注意：反向边的初始容量一定是 0，不是原边的容量。反向边的容量代表"可以撤销的流量"，初始时没有流量，所以是 0。这一点新手特别容易搞错。

3.2 BFS 分层函数的实现

bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queue<int> q; level[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (edge[i].cap > 0 && level[v] == -1) { level[v] = level[u] + 1; q.push(v); } } } return level[t] != -1; // 汇点可达则返回 true }

BFS 里有两个判断条件必须同时满足：边的剩余容量大于 0，且目标节点还没被分层。第一个条件保证只走残量网络中的边，第二个条件保证每个节点只被分层一次（取最短层号）。

有个小优化：如果 BFS 过程中已经访问到 T，其实可以提前退出，因为 T 的层号已经确定了。不过这个优化对正确性没影响，对性能提升也有限，看个人习惯。

3.3 DFS 增广函数的实现

int dfs(int u, int t, int flow) { if (u == t) return flow; for (int &i = cur[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (edge[i].cap > 0 && level[v] == level[u] + 1) { int d = dfs(v, t, min(flow, edge[i].cap)); if (d > 0) { edge[i].cap -= d; edge[i ^ 1].cap += d; return d; } } } return 0; }

这段代码有几个关键点。第一，int &i = cur[u]用了引用，这样 i 的每次自增都会直接修改 cur[u]，实现当前弧优化。第二，递归调用时传入的 flow 是min(flow, edge[i].cap)，保证不会超过路径上最小的剩余容量。第三，推送流量后，正向边容量减 d，反向边容量加 d，这是所有最大流算法的标准操作。

实操心得：DFS 的返回值设计成"本次推送的流量"，如果返回 0 说明当前节点已经无法再推送任何流量了。调用方收到 0 后应该继续尝试下一条边，而不是直接返回。

3.4 主循环的组装

int dinic(int s, int t) { int maxFlow = 0; while (bfs(s, t)) { memcpy(cur, head, sizeof(head)); // 每轮分层后重置当前弧 int f; while ((f = dfs(s, t, INF)) > 0) { maxFlow += f; } } return maxFlow; }

主循环的逻辑很清晰：只要 BFS 还能分层（说明还有增广路），就重置当前弧数组，然后反复 DFS 直到推不动为止。每轮分层结束后，maxFlow 累加本轮找到的所有增广路的流量。

这里有个容易忽略的点：memcpy(cur, head, sizeof(head))必须在每轮 BFS 之后执行。因为当前弧记录的是"本轮分层中每个节点扫描到哪条边了"，分层变了，之前的记录就失效了。

3.5 完整代码模板

把上面的片段拼起来，就是一份可以直接用的 Dinic 模板：

#include <bits/stdc++.h> using namespace std; const int MAXN = 10005; const int MAXM = 100005; const int INF = 0x3f3f3f3f; struct Edge { int to, cap, next; } edge[MAXM * 2]; int head[MAXN], cur[MAXN], level[MAXN], cnt; void init() { memset(head, -1, sizeof(head)); cnt = 0; } void addEdge(int u, int v, int cap) { edge[cnt] = {v, cap, head[u]}; head[u] = cnt++; edge[cnt] = {u, 0, head[v]}; head[v] = cnt++; } bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queue<int> q; level[s] = 0; q.push(s); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (edge[i].cap > 0 && level[v] == -1) { level[v] = level[u] + 1; q.push(v); } } } return level[t] != -1; } int dfs(int u, int t, int flow) { if (u == t) return flow; for (int &i = cur[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if (edge[i].cap > 0 && level[v] == level[u] + 1) { int d = dfs(v, t, min(flow, edge[i].cap)); if (d > 0) { edge[i].cap -= d; edge[i ^ 1].cap += d; return d; } } } return 0; } int dinic(int s, int t) { int maxFlow = 0; while (bfs(s, t)) { memcpy(cur, head, sizeof(head)); int f; while ((f = dfs(s, t, INF)) > 0) maxFlow += f; } return maxFlow; }

这份模板我用了很多年，改改 MAXN 和 MAXM 就能直接套。INF 取 0x3f3f3f3f 是个好习惯，两个 INF 相加不会溢出 int。

4. 复杂度分析与性能实测

4.1 理论复杂度是怎么算出来的

Dinic 的复杂度是 O(V²E)。这个上界怎么来的？分两部分看。

BFS 分层的次数最多是 O(V) 次。为什么？因为每轮分层后，最短增广路的长度至少增加 1，而增广路长度最多是 V-1（简单路径最多经过 V 个节点）。所以最多分层 O(V) 轮。

每轮分层中，DFS 的总复杂度是 O(VE)。这个稍微绕一点。在单轮分层中，每条边最多被"饱和"一次（即剩余容量被榨干），而每次饱和至少推送 1 单位流量。DFS 回溯时，一条边被废弃后不再访问（当前弧优化保证）。所以单轮中所有 DFS 的总边访问次数是 O(E)，但每次增广路可能很长，综合下来单轮复杂度是 O(VE)。

两部分相乘，得到 O(V²E)。注意这是最坏情况的上界，实际运行中 Dinic 通常远快于这个上界。在单位容量网络（每条边容量都是 1）中，Dinic 的复杂度是 O(E√V)，非常优秀。

4.2 不同图规模下的实测数据

我在本地做过一组测试，用随机生成的图跑 Dinic，数据仅供参考：

可以看到，即使在上万节点、二十万边的规模下，Dinic 也能在秒级完成。这个性能对于绝大多数竞赛题目和工程场景都够用了。

4.3 什么情况下 Dinic 会变慢

Dinic 最怕的是"长链式"的图结构，也就是增广路特别长、分层轮数特别多的图。比如一条从 S 到 T 的链，中间有 n 个节点，每条边容量都是 1。这种情况下每轮分层只能推 1 单位流量，需要 n 轮才能跑完，复杂度退化到 O(n²)。

还有一种情况是容量特别大的边。如果某条边容量是 10^9，DFS 每次只能推一部分，需要多次增广。不过这种情况通常不会太严重，因为每次增广至少能推 min(flow, cap) 的流量。

避坑技巧：如果发现 Dinic 跑得异常慢，先检查是不是忘了加当前弧优化，这是最常见的原因。其次检查 BFS 分层是否每轮都正确重置了 level 数组。

5. 常见问题与排查实录

5.1 死循环与栈溢出

DFS 递归写不好容易死循环。最常见的原因是分层条件写错，比如写成了level[v] >= level[u] + 1或者漏掉了level[v] == level[u] + 1的判断。一旦允许走同层或回退的边，DFS 就可能在环里打转。

另一个坑是递归深度。如果增广路很长（比如上万个节点），递归 DFS 可能爆栈。解决办法有两个：一是把 DFS 改成手写栈的迭代版本，二是增大编译器的栈空间。在竞赛中，如果图规模很大，我一般直接用迭代版本，稳妥。

5.2 流量推送不正确

有时候代码能跑，但结果偏小。排查方向：第一，检查反向边容量是否正确增加。正向减 d、反向加 d，这两步必须成对出现。第二，检查 addEdge 时反向边初始容量是否为 0。第三，检查 DFS 返回值是否正确累加。

我遇到过一次特别隐蔽的 bug：addEdge 里反向边的 next 指针写错了，导致反向边没有正确接入邻接表。这种错误不会报错，只会让结果偏小，非常难查。后来我养成了习惯，写完 addEdge 后立刻用一个小例子验证正反边的下标关系。

5.3 多源多汇怎么处理

很多实际问题不是单源单汇的。比如有多个仓库、多个门店，问最大运输量。解决办法是建一个超级源点 S' 和一个超级汇点 T'，从 S' 向每个真实源点连一条容量为 INF 的边，从每个真实汇点向 T' 连一条容量为 INF 的边，然后对 S' 和 T' 跑 Dinic。

这个技巧叫"超级源汇"，是网络流建模的基本功。容量设成 INF 是因为超级源到真实源的边不应该成为瓶颈，它只是起到"汇聚"的作用。

5.4 常见问题速查表

5.5 几个我踩过的坑

第一个坑：memset(level, -1, sizeof(level))里的 sizeof 如果写成sizeof(level[0])，只会重置第一个元素，后面的全是垃圾值。这个错误编译器不会报，但结果完全错乱。

第二个坑：当前弧数组 cur 忘记在每轮 BFS 后重置。表现是第二轮分层后 DFS 直接返回 0，结果偏小。因为 cur 还停留在上一轮的末尾位置。

第三个坑：INF 设得太大导致溢出。如果用0x7fffffff作为 INF，两个 INF 相加就溢出了。用0x3f3f3f3f更安全，它的两倍还在 int 范围内。

6. 从最大流到最小割的延伸

6.1 最大流最小割定理

学完最大流，一定要理解最小割。割是指将节点分成两个集合 S 和 T（源点在 S，汇点在 T），割的容量是所有从 S 指向 T 的边的容量之和。最小割就是容量最小的割。

最大流最小割定理指出：最大流的值等于最小割的容量。这个定理的直观理解是：最大流受限于最窄的那个"瓶颈"，而最小割恰好刻画了这个瓶颈。当算法结束时，残量网络中从源点可达的节点集合，就构成了一个最小割。

6.2 如何从残量网络提取最小割

Dinic 跑完后，在残量网络上从源点做一次 BFS（或 DFS），所有能到达的节点构成集合 S，其余节点构成集合 T。然后遍历所有原图中的边，如果一条边的起点在 S、终点在 T，且这条边是原图中的正向边，那么它就在最小割中。

这个技巧在解决"最小代价切断所有路径"类问题时非常有用。比如要切断所有从 S 到 T 的通路，最少需要删除多少容量的边，答案就是最小割，也就是最大流。

6.3 二分图匹配与最大流的关系

二分图最大匹配可以转化为最大流问题。建图方式：源点向左侧每个点连容量 1 的边，左侧点到右侧点如果有匹配关系就连容量 1 的边，右侧每个点向汇点连容量 1 的边。跑最大流，结果就是最大匹配数。

为什么容量都是 1？因为每个点最多匹配一次，每条匹配边最多用一次。这个转化是网络流建模的经典案例，理解了它，就能举一反三处理各种带约束的分配问题。

7. 写在最后的一些实战建议

Dinic 这个算法，看懂了和写对了是两回事，写对了和写快了又是两回事。我的建议是：先把模板背下来，能默写出来，然后找几道裸题练手，比如经典的"草地排水"类问题。等模板写熟了，再去理解每一行代码为什么这么写。

调试网络流代码有个笨办法但很有效：把图缩小到 3 到 5 个节点，手动模拟一遍算法流程，把每轮 BFS 的 level 数组和每轮 DFS 的增广路都打印出来，对照自己的预期检查。我当年就是靠这个方法把 Dinic 彻底搞懂的。

还有一点，网络流的难点从来不是算法本身，而是建模。给你一个实际问题，能不能抽象成最大流模型，源点汇点怎么设，边怎么连，容量怎么定，这才是真正考验功力的地方。Dinic 只是工具，建模才是核心。多做题、多总结模型，比死磕算法实现重要得多。

最后分享一个我常用的调试技巧：在 dfs 函数里加一行打印，输出当前节点、推送流量和剩余流量，跑一个小图，把输出和手算结果对比。这个方法能快速定位是分层错了、当前弧错了还是容量更新错了。踩过的坑多了，自然就有感觉了。