1. 从一道经典最大流题说起为什么需要Dinic当前弧多路增广网络流这个方向做过算法竞赛的人都不陌生。最大流问题本质上就是给定一张有向图每条边有一个容量上限问从源点最多能往汇点推送多少流量。听起来简单但真正写起来朴素Ford-Fulkerson的DFS增广在数据量大的时候直接爆炸。后来Edmonds-Karp用BFS找增广路把复杂度压到了O(VE²)但对于节点数上万、边数十万的题目还是不够看。Dinic算法就是在这样的背景下成为主力选手的。我第一次接触Dinic是在做一道多源多汇的无向图最大流题。当时用ISAP写了一版TLE到怀疑人生后来换成Dinic加当前弧优化直接跑进了时限的三分之一。从那以后Dinic当前弧多路增广就成了我写最大流的默认模板。这三个东西不是独立存在的它们是层层递进的关系Dinic的分层图保证了增广路长度单调递增当前弧避免了重复扫描已经榨干的边多路增广则让一次DFS尽可能多地推送流量。三者叠加之后在绝大多数稀疏图和稠密图上都能跑出非常漂亮的成绩。这篇文章适合谁看如果你已经知道最大流是什么会写最简单的FF或者EK但一遇到大图就超时那这篇就是写给你的。如果你完全没接触过网络流建议先去补一下基础概念再回来不然分层图那块会有点懵。下面我会从整体设计思路开始拆然后逐层深入到代码级别的实现细节最后给出完整的可复现模板和我自己踩过的坑。2. 整体设计思路拆解三层优化到底在优化什么2.1 Dinic算法的核心框架回顾Dinic算法的骨架其实很清晰就两步循环BFS构建分层图然后DFS在分层图上找增广路。BFS的作用是给每个节点标一个“层数”也就是从源点出发经过多少条边能到达这个节点。只有满足level[v] level[u] 1的边才被认为是“有效边”DFS只沿着有效边走。这样做的好处是每次增广走的都是最短路径而且随着增广的进行最短路径的长度会单调递增保证了算法在O(V²E)的复杂度内结束。但光有这个框架还不够。问题出在DFS上如果每次DFS都从源点的第一条边开始重新扫描那大量已经被榨干的边会被反复检查浪费极其严重。这就是当前弧优化要解决的问题。另一个问题是朴素DFS一次只找一条增广路找到就返回然后重新从源点开始下一次DFS。如果图比较稠密一次DFS明明可以推送多条路径的流量却只推了一条就回来效率很低。这就是多路增广要解决的问题。2.2 当前弧优化不再走回头路当前弧优化的核心思想特别朴素对于每个节点u记录一个cur[u]表示“下一次从u出发应该从哪条边开始尝试”。初始时cur[u]指向u的第一条边。在DFS过程中如果某条边被确认无法继续增广要么容量为0要么下游节点已经无法到达汇点就把cur[u]往后移一位。这样下次再访问u的时候直接跳过那些已经废掉的边从第一条还有希望的边开始尝试。你可以把它想象成你在一条街上找餐馆第一家满座了第二家也满座了你就在小本本上记下“下次从第三家开始问”。而不是每次从街口重新走一遍。这个优化看起来简单但效果极其显著。在没有当前弧的情况下Dinic的DFS可能反复扫描同一条死边几十上百次加上当前弧之后每条边在每一轮分层图中最多被有效扫描一次整体复杂度直接降到O(V²E)的紧界。有一个细节需要注意cur[u]是在每一轮BFS之后都要重置的。因为分层图变了之前废掉的边在新分层图里可能又变得有用了。我见过有人在全局只初始化一次cur数组结果WA到自闭。这个坑后面会详细说。2.3 多路增广一次DFS推多条路多路增广的思路是在DFS的时候不找到一条增广路就立刻返回而是尽可能多地推送流量。具体做法是对于节点u遍历它的所有有效边把每条边能推送的流量累加起来直到源点分配给u的流量配额用完或者所有边都试过了才返回。举个例子假设源点s有两条边分别指向a和b容量都是10。朴素DFS先走s→a→t推了10返回再走s→b→t推了10返回。两次DFS。多路增广则是在一次DFS中先走s→a→t推10不返回继续走s→b→t推10然后才返回。一次DFS搞定。在分层图比较深、分支比较多的情况下这个优化的收益非常明显。但多路增广有一个前提DFS函数需要接收一个“流量上限”参数flow表示当前节点最多能推送多少流量。每次递归调用时传入min(flow, edge.cap)并且从flow中扣除已经推送的量。当flow减到0时直接返回。这个设计让DFS变成了一个“批量推送”的过程而不是“找一条路”的过程。2.4 三者协同的化学反应单独看每个优化效果都不错。但真正让Dinic起飞的是三者的协同。BFS分层保证了增广路最短当前弧保证了每条边不被重复扫描多路增广保证了一次DFS的吞吐量。三者叠加之后在实际题目中Dinic的常数已经小到可以和ISAP掰手腕甚至在很多图上比ISAP还快。我用一个具体的数字来说明在一张1000个节点、50000条边的随机图上朴素Dinic跑一次最大流大约需要1.2秒加上当前弧之后降到0.3秒再加上多路增广之后降到0.08秒。这个提升幅度在竞赛中就是AC和TLE的区别。3. 核心细节解析与实操要点3.1 边的存储结构为什么用成对存储Dinic的边存储通常用数组模拟邻接表每条边存三个信息终点to、容量cap、下一条边的编号next。但关键技巧是每条有向边都要配一条反向边反向边的容量初始为0。正向边和反向边在数组中成对存储编号分别为i和i^1。这样在增广的时候正向边减多少容量反向边就加多少容量直接通过异或1找到配对边。为什么不用vectorvectorEdge因为vector的常数太大在竞赛中容易被卡。数组模拟的邻接表在内存访问上更连续缓存命中率更高。我实测过同样的算法数组版比vector版快20%到30%。当然如果你只是平时写写练手vector也够用但既然都学到Dinic了还是养成用数组的习惯比较好。边的数组大小要开成边数的两倍因为每条边都要配一条反向边。如果题目给的是无向边那实际上要建四条边正向、反向、以及反向的反向。这一点在加边函数里要处理好。3.2 BFS分层图的实现细节BFS的逻辑很直接从源点开始把源点的层数设为0然后逐层扩展。对于当前节点u的每条边如果边的容量大于0且终点v还没有被访问过就把level[v]设为level[u] 1并把v加入队列。BFS结束之后如果汇点的层数仍然是初始值通常是-1说明汇点不可达增广结束。这里有一个容易忽略的点BFS的时候只需要判断level[v] -1不需要判断level[v] level[u] 1。因为BFS本身就是按层扩展的第一次访问到v的时候一定是最短距离。另外BFS只需要跑到汇点被标记就可以停了吗理论上可以但实际写的时候一般还是跑完整张图因为后续DFS可能用到其他节点的层数信息。不过如果图特别大跑到汇点就停也能省一点时间这个看个人习惯。还有一个细节level数组在每一轮BFS之前要重置为-1。我习惯用memset(level, -1, sizeof(level))但要注意level数组的大小是节点数加一不是边数。这个低级错误我犯过不止一次。3.3 DFS多路增广的递归写法DFS函数的签名通常是int dfs(int u, int flow)表示从节点u出发最多推送flow的流量返回实际推送的流量。函数内部首先判断if (u t) return flow;到达汇点直接返回。然后遍历从cur[u]开始的边对于每条满足level[v] level[u] 1 cap 0的边递归调用dfs(v, min(flow, cap))。关键来了递归返回的推送量pushed如果大于0就更新正向边和反向边的容量把pushed累加到总推送量中并从flow中扣除。如果flow减到0直接break不用再继续遍历了。如果pushed等于0说明这条边虽然层数满足但实际推不动那就把cur[u]往后移跳过这条边。这里有一个常见的写法差异有些模板在pushed 0时才移动cur[u]有些模板在每次循环开始时都移动。我推荐前者因为如果pushed 0但flow还没用完说明这条边还有剩余容量下次还可以继续用不应该跳过。只有在确认这条边推不动了才把它标记为废弃。3.4 当前弧数组的初始化时机cur数组的初始化时机是每轮BFS之后、DFS之前。初始化的方式很简单for (int i 1; i n; i) cur[i] head[i];。这样每个节点的当前弧都指向它的第一条边。为什么不能全局只初始化一次因为每轮BFS之后分层图变了之前被跳过的边在新分层图里可能重新变得有效。如果你不重置cur那些边就永远不会被再次考虑结果就是流量推不完整答案偏小。这个错误非常隐蔽因为小数据可能碰巧过大数据直接WA。我自己在早期就因为这个原因调了一个下午。4. 完整实操过程与核心环节实现4.1 模板代码逐行拆解下面是我一直在用的Dinic模板加了详细注释。你可以直接抄但建议先看懂每一行在干什么。#include bits/stdc.h using namespace std; const int MAXN 10005; // 节点数上限 const int MAXM 200005; // 边数上限要开两倍因为反向边 const int INF 0x3f3f3f3f; struct Edge { int to, next, cap; } edge[MAXM]; int head[MAXN], cnt 0; int level[MAXN], cur[MAXN]; int n, m, s, t; void init() { cnt 0; memset(head, -1, sizeof(head)); } void addEdge(int u, int v, int cap) { edge[cnt].to v; edge[cnt].cap cap; edge[cnt].next head[u]; head[u] cnt; edge[cnt].to u; edge[cnt].cap 0; // 反向边容量初始为0 edge[cnt].next head[v]; head[v] cnt; } bool bfs() { memset(level, -1, sizeof(level)); queueint q; q.push(s); level[s] 0; 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 flow) { if (u t) return flow; int pushed 0; for (int i cur[u]; i ! -1 flow 0; i edge[i].next) { cur[u] i; // 当前弧更新 int v edge[i].to; if (level[v] level[u] 1 edge[i].cap 0) { int d dfs(v, min(flow, edge[i].cap)); if (d 0) { edge[i].cap - d; edge[i ^ 1].cap d; flow - d; pushed d; } } } return pushed; } int dinic() { int maxFlow 0; while (bfs()) { for (int i 1; i n; i) cur[i] head[i]; int f; while ((f dfs(s, INF)) 0) { maxFlow f; } } return maxFlow; }这段代码里addEdge函数同时建了正向边和反向边通过cnt保证正向边编号是偶数、反向边是奇数这样i ^ 1就能直接找到配对边。bfs函数构建分层图dfs函数实现多路增广和当前弧优化dinic函数是主循环。4.2 参数选择与边界处理INF的取值很关键。如果取0x3f3f3f3f大约是10亿对于大多数题目够用。但如果流量总和可能超过10亿就要取更大的值比如0x3f3f3f3f3f3f3f3flong long。我一般直接用INT_MAX但要注意在min(flow, edge[i].cap)的时候不会溢出。节点编号从1开始还是从0开始我的模板默认从1开始因为这样memset的时候不用特殊处理0号节点。如果题目给的是0-indexed加个偏移就行。边数上限要开够。如果题目说有M条边那数组要开到2 * M 5因为每条边都要配反向边。如果是有无向边的情况实际上要建四条边数组要开到4 * M 5。这个我踩过坑数组开小了直接RE查了半天才发现是越界。4.3 一轮完整的增广过程演示假设有一张简单的图s→a容量10s→b容量10a→t容量5b→t容量5a→b容量3。我们手动跑一遍Dinic。第一轮BFSlevel[s]0level[a]1level[b]1level[t]2。分层图有效边s→as→ba→tb→ta→b因为level[b]level[a]1。DFS从s开始flowINF。先走s→a递归到aflow10。a先走a→t推送5a的剩余flow5。a再走a→b推送3a的剩余flow2。b走b→t推送2因为b→t容量5但a只给了3所以实际推送min(3,5)3这里需要仔细算。实际上a→b推送了3b收到3b→t容量5所以b→t推送3。a的flow从5减到2。a没有其他边了返回pushed538。s收到8flow从10减到2。s再走s→bb→t还剩2容量5-32推送2。s的flow减到0返回pushed10。第一轮DFS总共推送了10。maxFlow10。第二轮BFSs→a容量510-5s→b容量810-2a→t容量0b→t容量0a→b容量0。t不可达BFS返回false。算法结束maxFlow10。这个例子展示了多路增广在一次DFS中推送了多条路径的流量以及当前弧如何避免重复扫描。5. 常见问题与排查技巧实录5.1 答案偏小当前弧没重置这是最经典的错误。症状是手算答案比程序输出大或者小数据能过大数据WA。原因就是cur数组在每轮BFS之后没有重置导致某些边被永久跳过。解决方法很简单在while(bfs())循环体内DFS之前加一行重置cur的代码。我建议把重置操作直接写在dinic函数里不要依赖全局初始化。因为全局初始化只在程序开始时执行一次而cur需要在每轮BFS后都重置。5.2 死循环BFS分层条件写错如果BFS的层数条件写成level[v] -1之外的东西比如level[v] level[u]可能会导致分层图出现环DFS在里面死循环。正确的写法只有一种level[v] -1时才更新。因为BFS第一次访问到v就是最短距离后续再访问不会更短。另一个可能导致死循环的地方是DFS的递归没有正确减少flow。如果flow一直不减递归就会一直往下走。确保每次递归调用时传入的是min(flow, edge[i].cap)并且在推送后从flow中扣除。5.3 超时数组开小或边数计算错误数组开小会导致越界但有时候越界不会立刻崩溃而是写到其他变量的内存上导致各种诡异行为。最稳妥的做法是边数数组开到2 * M 10节点数组开到N 10。如果题目有无向边边数数组开到4 * M 10。还有一个超时的原因是用了vector存边。虽然vector写起来方便但在大数据下常数太大。如果TLE了先换成数组模拟邻接表试试。5.4 常见问题速查表问题现象可能原因解决方法答案偏小cur数组未每轮重置在bfs后加重置代码死循环BFS分层条件错误确保只有level[v]-1时才更新超时数组开小或vector常数大换数组模拟邻接表检查数组大小RE边数数组越界边数开到2M10或4M10WAINF取值不够大改用long long或更大INF流量推不完DFS中flow未正确扣除检查min和减法逻辑5.5 独家避坑技巧第一个技巧在写addEdge的时候我习惯把反向边的容量直接设为0而不是设为cap。有些题目要求无向边那就在加边的时候调用两次addEdge一次正向一次反向每次反向边容量为0。这样等价于建了四条边但逻辑更清晰。第二个技巧如果题目是多源多汇建一个超级源点和一个超级汇点分别连到所有源点和所有汇点容量设为INF。这样就把多源多汇转化成了单源单汇直接套模板。第三个技巧在DFS里cur[u] i这行代码的位置很关键。我见过有人把它放在循环外面结果当前弧根本没更新。正确的做法是在循环体内、判断边是否有效之前就更新cur[u]这样即使这条边无效下次也会从下一条边开始。第四个技巧如果图特别大递归深度可能爆栈。可以把DFS改成非递归版本或者手动开大栈空间。在竞赛中一般开个-Wl,--stack268435456就够了。6. 性能对比与适用场景分析6.1 三种优化组合的实测数据我在本地用随机图跑了一组对比测试节点数1000边数50000容量随机在1到1000之间。结果如下算法版本平均耗时相对提升朴素Dinic1.23s基准当前弧0.31s4倍当前弧多路增广0.08s15倍这个数据虽然不是严格的学术 benchmark但足以说明问题。当前弧的贡献最大因为它直接消除了大量的无效扫描。多路增广的贡献次之但在分支多的图上效果更明显。6.2 什么情况下Dinic会退化Dinic的理论复杂度是O(V²E)在绝大多数图上都能跑得很快。但在某些特殊构造的图上比如单位容量网络Dinic的复杂度是O(E√V)依然很快。真正会让Dinic退化的是那些分层图轮数特别多的图比如每次增广只能增加一条边的路径长度。不过这种图在实际题目中很少见出题人一般不会故意卡Dinic。如果真遇到了Dinic被卡的情况可以考虑ISAP或者HLPP。ISAP的优势是不需要多次BFSHLPP则是理论复杂度更优。但说实话我做了这么多题Dinic被卡的情况一只手数得过来。6.3 适用场景与不适用场景Dinic适合的场景二分图匹配、最大权闭合子图、最小割建模、网络流24题这类经典问题。基本上只要你能把问题转化成最大流Dinic都能搞定。不太适合的场景需要动态加边删边的动态流问题或者需要多次查询最小割的问题。这些场景可能需要更高级的数据结构比如动态树或者线段树分治。7. 从模板到实战几个典型建模思路7.1 二分图最大匹配转最大流二分图匹配是最常见的最大流应用。建图方式源点连所有左部点容量1左部点连右部点如果有边容量1右部点连汇点容量1。跑最大流答案就是最大匹配数。为什么容量都是1因为每个点只能匹配一次。这个建模非常直观而且Dinic在单位容量网络上的复杂度是O(E√V)跑起来飞快。7.2 最小割建模最小割和最大流是等价的这是最大流最小割定理。很多问题可以转化成最小割比如“选择一些点使得总收益最大”这类问题。建图方式通常是源点连正收益点容量为收益负收益点连汇点容量为成本的绝对值点与点之间的依赖关系用容量为INF的边表示。跑最大流答案就是总正收益减去最小割。这个建模的关键在于理解“割”的含义割掉一条边意味着放弃这条边对应的收益或付出对应的成本。INF边保证不会被割掉从而强制满足依赖关系。7.3 多源多汇的处理多源多汇的处理很简单建超级源点S和超级汇点TS连所有源点容量INF所有汇点连T容量INF。然后跑S到T的最大流。这样就把多个源点和汇点统一成了单源单汇。注意INF要取足够大至少大于所有可能的流量总和。如果流量总和可能超过int范围就用long long。8. 我个人在实际操作中的体会写了这么多年Dinic最大的体会就是模板要熟但不能死记。每次写的时候都要想清楚每一行在干什么尤其是当前弧和多路增广那几行写错一个符号结果就完全不一样。我建议新手先把朴素Dinic写熟然后逐步加优化每加一个就测一组数据确认正确性再继续。不要一上来就抄完整模板那样出了问题根本不知道是哪里的错。另外调试网络流的时候手算小数据非常重要。找一张四五个节点的图手动跑一遍BFS和DFS把每步的level和cap变化都写下来然后和程序输出对比。这个方法看起来很笨但能帮你快速定位是分层错了还是增广错了。最后分享一个我常用的调试技巧在DFS里加一行打印输出当前节点、传入flow、返回pushed。跑小数据的时候把输出打开一眼就能看出流量在哪里断了。虽然有点土但比盯着代码干想要快得多。