网络流这个问题我在刚接触算法竞赛那会儿被它折磨得不轻。当时看到最大流三个字觉得挺直观——不就是让水从源点流到汇点管子粗细有限问最多能流多少嘛。真上手写代码才发现里面的门道比想象中多得多。今天就把我这些年反复踩坑、反复重构后沉淀下来的 Dinic 算法实现思路完整地摊开讲一遍。不管你是刚学完图论基础、准备啃网络流这块硬骨头的算法新手还是写过 EK 算法但被卡了常数、想升级到 Dinic 的老手这篇内容应该都能让你少走一些弯路。1. 最大流问题到底在解决什么1.1 从一个生活场景理解最大流先别急着看公式。想象你是一个物流调度员手头有一张运输网络图货物从仓库源点 S出发经过若干个中转站最终要送到门店汇点 T。每两个节点之间的运输通道都有固定的日承载上限也就是容量。你的任务是在不超载任何一条通道的前提下让从仓库发出的货物总量尽可能大。这就是最大流问题的本质。把它抽象成图论语言给定一个有向图每条边有一个非负容量 cap指定源点 S 和汇点 T求从 S 到 T 的最大可行流量。所谓可行要同时满足两个约束——容量限制每条边的实际流量不超过它的容量和流量守恒除了源点和汇点每个中间节点的流入总量等于流出总量。流量守恒这条约束特别关键很多人一开始会忽略它。你可以这样理解中转站不囤货进来多少就得出去多少不能凭空多出来也不能凭空消失。源点相当于无限供货汇点相当于无限收货只有这两个点允许收支不平衡。1.2 为什么不能贪心直接流新手最容易犯的错误就是找到一条从 S 到 T 的路径能流多少流多少然后重复这个过程直到找不到路径。这个思路叫贪心增广问题在于它可能做出错误的决策。举个经典的反例。假设 S 到 A 容量 1S 到 B 容量 1A 到 B 容量 1A 到 T 容量 1B 到 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 而不是 i1 或 i-1因为异或运算不需要判断奇偶无论 i 是奇数还是偶数i^1 都能正确得到配对边的下标。如果正边下标是偶数 2k反边就是 2k1如果正边是奇数 2k1反边就是 2k。这个技巧在竞赛代码里非常常见能省掉不少 if 判断。注意反向边的初始容量一定是 0不是原边的容量。反向边的容量代表可以撤销的流量初始时没有流量所以是 0。这一点新手特别容易搞错。3.2 BFS 分层函数的实现bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint 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)); queueint 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数据仅供参考节点数边数最大流值运行时间100500约 50 1ms5005000约 200约 5ms100020000约 400约 30ms5000100000约 2000约 400ms10000200000约 4000约 1.2s可以看到即使在上万节点、二十万边的规模下Dinic 也能在秒级完成。这个性能对于绝大多数竞赛题目和工程场景都够用了。4.3 什么情况下 Dinic 会变慢Dinic 最怕的是长链式的图结构也就是增广路特别长、分层轮数特别多的图。比如一条从 S 到 T 的链中间有 n 个节点每条边容量都是 1。这种情况下每轮分层只能推 1 单位流量需要 n 轮才能跑完复杂度退化到 O(n²)。还有一种情况是容量特别大的边。如果某条边容量是 10^9DFS 每次只能推一部分需要多次增广。不过这种情况通常不会太严重因为每次增广至少能推 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 返回值是否正确累加。我遇到过一次特别隐蔽的 bugaddEdge 里反向边的 next 指针写错了导致反向边没有正确接入邻接表。这种错误不会报错只会让结果偏小非常难查。后来我养成了习惯写完 addEdge 后立刻用一个小例子验证正反边的下标关系。5.3 多源多汇怎么处理很多实际问题不是单源单汇的。比如有多个仓库、多个门店问最大运输量。解决办法是建一个超级源点 S 和一个超级汇点 T从 S 向每个真实源点连一条容量为 INF 的边从每个真实汇点向 T 连一条容量为 INF 的边然后对 S 和 T 跑 Dinic。这个技巧叫超级源汇是网络流建模的基本功。容量设成 INF 是因为超级源到真实源的边不应该成为瓶颈它只是起到汇聚的作用。5.4 常见问题速查表问题现象可能原因排查方法结果偏小反向边容量未增加检查edge[i^1].cap d结果偏小反向边初始容量不为 0检查 addEdge 第二行死循环分层条件写错确认是不是栈溢出递归深度过大改迭代或增大栈空间运行超时缺少当前弧优化检查int i cur[u]结果为 0源汇不连通检查 BFS 返回值结果偏大流量守恒被破坏检查 DFS 的 flow 参数传递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 函数里加一行打印输出当前节点、推送流量和剩余流量跑一个小图把输出和手算结果对比。这个方法能快速定位是分层错了、当前弧错了还是容量更新错了。踩过的坑多了自然就有感觉了。