我面试过一位候选人三分钟把 Dinic 算法模板敲完代码很干净。我问他这个算法的复杂度分析为什么是 O(V²E)他愣了几秒回答“每次 BFS O(E)最多 V 次每次 DFS 也是 O(E)吧”这个回答当然不对但很有代表性——很多人的 Dinic 是背下来的不是理解下来的。这篇文章想把这套复杂度分析讲透为什么阶段数只有 O(V)为什么单个阶段能做到 O(VE)以及这两个结论怎么拼成最终的 O(V²E)。如果你正在学网络流、准备算法竞赛或者只是想把板子背后那层纸捅破都值得往下看。我会把证明写成可以直接复述的形式最后再聊几个让复杂度真正落地到代码里的坑。1. 先聊结论O(V²E) 到底在说什么1.1 记号约定在进入证明之前先把记号定死否则后面很容易绕晕。本文讨论的是有向网络 (G(V,E))(s) 是源点(t) 是汇点每条有向边有一个非负容量。剩余网络 (G_f) 表示当前流量 (f) 下还有多少容量可用所谓距离就是剩余网络中从 (s) 到某个点的最短路径边数。Dinic 的每一轮都先用 BFS 从 (s) 出发计算 (level[v]dist_f(s,v))然后把满足 (level[v]level[u]1) 且有剩余容量的边 ((u,v)) 保留下来。这张子图就是层次网络。层次网络有一个很重要的性质它一定是有向无环图因为每条边都从第 (i) 层指向第 (i1) 层不可能绕回同一层或更低层。后面证明阶段数上界时靠的就是这个层级结构。1.2 把结论拆成三块复杂度结论不是从天而降的。整体上Dinic 就是“建层次图、找阻塞流、再建层次图”的循环。这个循环次数受“距离严格递增”限制每一轮距离最多到 (V-1)所以至多 (V) 轮。每一轮里BFS 分层是 (O(VE))DFS 找阻塞流是 (O(VE))。把账加在一起主项就是 (V) 个阶段乘以 (O(VE))得到 (O(V^2E))。部分单次上界累计上界BFS 分层(O(VE))(O(V^2VE))找阻塞流(O(VE))(O(V^2E))阶段数(O(V))不影响上面主项这里说的 (E) 是原图边数不是实现里加了反向边之后的边数。实际代码通常会存 (2E) 条有向边常数会翻倍但量级仍然是 (O(V^2E))。2. 层次网络和阻塞流Dinic 真正聪明的两个操作2.1 BFS 分层为什么只看相邻层很多初学者不理解为什么要用 BFS而且只保留相邻层之间的边原因是 Dinic 每个阶段只处理当前剩余网络里最短的 (s \to t) 路。BFS 天然算出从 (s) 出发的逐层距离如果一条边满足 (level[v]level[u]1)说明它有可能出现在一条最短路上。那些跳到同一层、跳回低层的边不可能出现在当前最短路上这个阶段直接忽略。这种“只处理最短路”的设计是 Dinic 比朴素增广路算法快的关键。朴素算法每次随便找一条增广路路径长度可能忽长忽短Dinic 则先把当前最短距离的所有路“堵住”下一阶段再考虑更长的路。于是每一轮结束之后最短路的长度一定变大阶段数就有了明确上界。2.2 “阻塞流”不是最大流千万别混在层次网络里找的流叫阻塞流。它的定义是层次网络中的每条 (s \to t) 路径都至少有一条边被压满。注意阻塞流不一定是原图最大流因为原图可能还存在更长的绕行路径。打个比方你在一栋楼里从一楼到顶楼每层电梯都堵了一条通道但楼梯还能走那些楼梯就是更长路径。阻塞流还有一个等价说法在层次网络里已经不存在 (s \to t) 的增广路。因为每一条路都至少有一个瓶颈边被压满没法再向 (t) 推送正流量。Dinic 一个阶段的任务就是找到这样的阻塞流如果找不到说明当前层次网络已经推不动了必须重新 BFS 构建新的层次网络。2.3 当前弧优化在复杂度里的准确位置好多模板都把当前弧优化当成普通常数优化其实它远远不止是常数优化。它的作用在于当 DFS 在某条边上失败后当前弧指针会跳过这条边并且这个阶段内再也不会回头尝试它。这就保证了“每条失败边只被扫一次”。如果没有当前弧优化一条边可能被反复扫几百遍最坏情况下一个阶段的复杂度就不再是 (O(VE))。后面证明时的“失败尝试总次数 (O(E))”完全依赖当前弧优化所以它是证明的一环不是可有可无的锦上添花。3. 阶段数为什么至多 O(V)一条反证法3.1 核心引理这一步是整个复杂度分析的第一个硬骨头。设某一轮开始时的最短距离是 (d)找完阻塞流之后下一轮的最短距离至少是 (d1)。换句话说Dinic 的每一轮都会让 (s \to t) 的距离严格增加至少 1。这个引理很多人只记住了结论没有真正理解为什么。下面我用反证法把它写完整。只要能复述这个证明阶段数 (O(V)) 就是水到渠成的事。3.2 反证法细节假设找完阻塞流之后新剩余网络里存在一条 (s \to t) 路径 (P)长度是 (m \le d)。对每个点 (v)记 (h(v)) 为旧一轮 BFS 算出的距离也就是阶段开始前的 (dist_f(s,v))。显然 (h(s)0)而 (h(t)d)。现在看路径 (P) 上的每条边 ((x,y))分两类讨论。第一类这条边在旧一轮开始前就存在于剩余网络。那么因为从 (s) 到 (x) 已经有长度 (h(x)) 的路径再接上边 ((x,y))就得到一条长度 (h(x)1) 的到 (y) 的路径所以一定有 (h(y) \le h(x)1)。第二类这条边是本轮增广时新产生的反向边。增广只沿着旧层次网络中的边进行所以这条新反向边必然来自旧层次网络里的某条边 ((y,x))并且旧层次网络满足 (h(x)h(y)1)。整理一下就是 (h(y)h(x)-1)。无论哪一类都能得到 (h(y) \le h(x)1)。把路径 (P) 从起点到终点一路叠加起来就有[ h(t) \le h(s)m m ]但 (h(t)d)所以 (d \le m)。题目又假设 (m \le d)于是只能 (md)而且路径上每一步的不等式都必须取等号。第二类边会得到 (h(y)h(x)-1)不可能取等号所以路径 (P) 不可能包含本轮新增的反向边。第一类边取等号时说明 (h(y)h(x)1)这条边正好是旧层次网络里的边。这样(P) 就是一条完全由旧层次边组成的 (s \to t) 路径。但这一轮已经找过阻塞流。所谓阻塞流意味着旧层次网络里每条 (s \to t) 路径都至少有一条边被压满剩余容量为 0。(P) 如果还能完整出现在新剩余网络里说明 (P) 上所有边都还有正剩余容量这就和阻塞流的定义矛盾。所以原假设不成立新剩余网络中不存在长度不超过 (d) 的 (s \to t) 路径。新距离至少是 (d1)。这个证明的妙处在于它用旧距离给路径“计价”。新增反向边只能让旧距离减小 1根本“付不起”保持最短路径所需的每一步 (1)一旦出现这类边路径总长度就不可能再压到 (d) 或更短。3.3 为什么不可能出现无限循环由上面的引理每完成一个阶段(s \to t) 的距离都严格增加至少 1。而剩余网络里如果存在一条 (s \to t) 路径就一定存在一条不经过重复顶点的简单路径长度最多 (V-1)。因此距离最大也只能是 (V-1)阶段数至多为 (V)。这里的 (O(V)) 是一个很宽松的上界实际跑起来往往远小于 (V)但作为理论保证已经够了。这个结论还有一层含义Dinic 不会因为反向边的存在而陷入某个阶段的局部循环。反向边只在下一轮重新 BFS 时发挥作用它让距离标号发生改变但绝不会让本轮距离倒退。4. 单个阶段为什么是 O(VE)摊还视角看 DFS4.1 每次成功增广至少饱和一条边阶段数证明完之后剩下要算的是“一个阶段的阻塞流到底花多少时间”。阻塞流的典型实现是反复从 (s) 出发调用 DFS能推多少推多少直到 DFS 返回 0。在层次网络里所有 (s \to t) 路径长度都等于当前距离 (d)并且 (d \le V-1)。每次 DFS 从 (s) 成功走到 (t)都会沿着路径推送一定流量这个流量由路径上的瓶颈边决定所以至少会有一条边的剩余容量变成 0。这里要多想一步被压满的边会不会在同一个阶段里被反向边“救回来”不会。因为增广产生的新反向边从高层指向低层不满足 (level[v]level[u]1) 这个层次条件它不属于本阶段层次网络。也就是说一条层次边一旦被压满它在当前阶段就永久消失了。初始层次网络里的边数不超过原图边数 (E)所以成功增广的次数不超过 (E)。4.2 失败尝试每条边只发生一次除了成功增广DFS 里还有大量失败尝试。比如一个节点往下走发现子节点已经无法到达 (t)于是 DFS 返回 0父节点就把这条边跳过。用当前弧优化的话每个节点维护指针 (it[u])指针只会向后移动不会回退。因此每条边作为“失败候选”最多被处理一次。把图中所有节点的出边数加起来就是层次网络里的边数最多 (E)。所以整个阶段中失败扫描的总次数是 (O(E))。这里的关键不是“DFS 本身多聪明”而是当前弧优化让每一次失败都变成永久性放弃不会再造成重复劳动。4.3 把 DFS 的花费逐项加总现在把成功和失败两部分加在一起。成功增广最多 (E) 次每次路径长度最多 (V-1)因此成功扫描的代价是 (O(VE))。失败扫描总共 (O(E))。再加上这一阶段开始时的 BFS 分层 (O(VE))单阶段总复杂度就是 (O(VE))。由于 (V \ge 1)那点 BFS 开销被主项吸收通常直接记作 (O(VE))。这就是“单阶段 O(VE)”的完整来源。它不是一个粗略估计而是一个摊还分析成功路径的代价按路径长度算失败代价按边的数量算两边都没有漏掉。5. 把三段拼起来O(V²E) 的完整证明链5.1 总时间怎么加总把前两节的结果放到同一个式子里就是[ \sum_{\text{阶段}} \left( O(VE) O(VE) \right) O(V^2 VE) O(V^2E) O(V^2E) ]阶段数 (O(V)) 是第一个乘数单阶段阻塞流 (O(VE)) 是第二个乘数两者相乘得到了主项 (O(V^2E))。BFS 的贡献只有 (O(VE)) 甚至更小不会改变量级。需要强调一下这里的复杂度是指数级别上的理论最坏情况。它不是“平均表现”也不是“实践中一定达到”而是一个可以证明的、无论在什么图上都不会被突破的上界。5.2 候选人的误区在哪里文章开头那位候选人说“每次 DFS 也是 O(E)”这就是混淆了“一条增广路径的代价”和“一个阶段的总代价”。单次 DFS 从 (s) 出发沿一条链走到底递归深度最多 (V)所以代价是 (O(V))不是 (O(E))。一个阶段里成功增广次数最多 (E)于是总代价是 (O(E) \times O(V)O(VE))。如果再乘上阶段数 (O(V))才得到最终 (O(V^2E))。常见错误结论是把增广次数算成 (O(E))、每次路径长度算成 (O(E))于是得到 (O(VE^2)) 之类的界。之所以错是因为层次网络里的路径长度被限制成了当前最短距离 (d)而不是任意剩余网络里的路径长度。5.3 复杂度结论的适用前提这套证明依赖标准实现必须有当前弧优化必须有成对存储的反向边必须每个阶段重置当前弧指针BFS 也必须只走剩余容量大于 0 的边。少掉任何一条证明中的某个关键上界就会失效。比如不重置it上一阶段的指针会错误地跳掉本阶段的新边反向边存储不对更新容量可能从 (O(1)) 变成 (O(E))单次增广代价直接拉满。很多人抱怨 Dinic 跑得慢其实不是算法慢而是板子里某个细节破坏了复杂度成立的前提。6. 实现里那些让复杂度“破功”的点6.1 标准 Dinic 骨架先给一份最贴合上面证明的标准实现再解释它和复杂度分析是怎么对应的。struct Edge { int to, rev; long long cap; }; vectorEdge g[MAXN]; int level[MAXN], it[MAXN]; int n; void add_edge(int u, int v, long long c) { Edge a{v, (int)g[v].size(), c}; Edge b{u, (int)g[u].size(), 0}; g[u].push_back(a); g[v].push_back(b); } bool bfs(int s, int t) { fill(level, level n, -1); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (const Edge e : g[u]) { if (e.cap 0 level[e.to] -1) { level[e.to] level[u] 1; q.push(e.to); } } } return level[t] ! -1; } long long dfs(int u, int t, long long f) { if (u t) return f; for (int i it[u]; i (int)g[u].size(); i) { Edge e g[u][i]; if (e.cap 0 level[e.to] level[u] 1) { long long ret dfs(e.to, t, min(f, e.cap)); if (ret 0) { e.cap - ret; g[e.to][e.rev].cap ret; return ret; } } } return 0; } long long dinic(int s, int t) { long long ans 0; while (bfs(s, t)) { fill(it, it n, 0); while (long long pushed dfs(s, t, INF)) { ans pushed; } } return ans; }这段代码里最影响复杂度的两行是for (int i it[u]; ...)和level[e.to] level[u] 1。前者保证失败边只被跳一次后者保证 DFS 永远不会走出层次网络路径长度锁死在当前距离 (d)。去掉任何一个上面的证明都不再成立。6.2 常见板子问题第一rev的下标必须正确。add_edge里正向边的rev指向反向边在g[v]中的位置反向边的rev指向正向边在g[u]中的位置。如果不小心在push_back前后取错下标更新的就是别的边正确性直接崩。第二it数组必须在每一轮 BFS 之后重置而不是每次 DFS 前重置。一句话记法it属于“阶段”不属于“单次增广”。它记录的是本阶段中哪些边已经被放弃了换阶段后所有边的状态都要清零。第三BFS 里判断e.cap 0必须是严格大于 0。有人写成e.cap 0结果流量为 0 的边也能进入层次网络DFS 会在无效边上反复递归复杂度瞬间变成无法分析的怪物。这个问题平时可能不触发一旦触发就是最难查的 bug。第四容量类型尽量用long longINF初始化成足够大的数。如果INF小于真实最大流一次 DFS 可能只推送很小流量间接增加增广次数。虽然理论上复杂度上界没变但常数会变得非常难看。6.3 什么时候会真的慢理论上确实可以构造出让 Dinic 跑满 (V) 个阶段、每个阶段几乎遍历全图的例子此时复杂度逼近 (O(V^2E))。这通常需要精心设计分层结构和容量分布不是随便一个随机图都能达到。实践中Dinic 在绝大多数图上跑的阶段数都远小于 (V)尤其是边容量不太极端的时候。但作为算法使用者不能因为“平时快”就忽略证明。遇到构造卡数据的题目知道复杂度上界能帮你判断要不要换算法或者至少先怀疑是不是板子细节破坏了摊还。6.4 单位容量图上的额外优势如果图上每条边的容量都是 1单位容量图会有更强结论阶段数可以压到 (O(\sqrt V)) 这个量级。最典型的应用是二分图最大匹配把源点连左部点、左部点连右部点、右部点连汇点所有边容量为 1Dinic 的行为就和 Hopcroft-Karp 算法非常接近实际表现远好于一般网络流。这也是为什么竞赛里有人说“Dinic 跑二分图匹配很快”。它不是玄学而是特殊容量结构让阶段数的上界变得更紧。理解了这个你就知道什么时候可以放心裸奔 Dinic什么时候该考虑更专门的算法。7. 最后分享两个我实际写板子时的习惯7.1 用对拍验证正确性也验证复杂度我调试 Dinic 时会先在随机小图和朴素增广路算法对拍确认最大流结果一致。如果偶尔出现某张图跑得特别慢我不会立刻怀疑复杂度结论而是先查当前弧有没有重置、反向边下标对不对、BFS 是否严格判了剩余容量。经验告诉我绝大多数“Dinic 被卡”其实是板子被卡不是算法被卡。7.2 把证明要点写成注释我的板子里通常会留三行注释阶段数 O(V) 来自距离严格递增单阶段 O(VE) 来自失败边只扫一次加成功增广不超过 E最终 O(V²E)。这样过几个月再回头看不用重新推一遍也能马上想起每个优化到底在保护哪个上界。复杂度证明看起来绕但它不是刁钻题而是告诉你哪些优化动不得。理解了这条链之后Dinic 才真正变成一个可以改的算法而不是一段不能碰的模板。