Dinic算法复杂度O(V²E)详解：从阻塞流到当前弧优化

我面试过一位候选人，三分钟把 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) 层指向第 (i+1) 层，不可能绕回同一层或更低层。后面证明阶段数上界时，靠的就是这个层级结构。

1.2 把结论拆成三块

复杂度结论不是从天而降的。整体上，Dinic 就是“建层次图、找阻塞流、再建层次图”的循环。这个循环次数受“距离严格递增”限制；每一轮距离最多到 (V-1)，所以至多 (V) 轮。每一轮里，BFS 分层是 (O(V+E))，DFS 找阻塞流是 (O(VE))。把账加在一起，主项就是 (V) 个阶段乘以 (O(VE))，得到 (O(V^2E))。

这里说的 (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)，找完阻塞流之后，下一轮的最短距离至少是 (d+1)。换句话说，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)，于是只能 (m=d)，而且路径上每一步的不等式都必须取等号。

第二类边会得到 (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) 路径。新距离至少是 (d+1)。

这个证明的妙处在于，它用旧距离给路径“计价”。新增反向边只能让旧距离减小 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)：摊还视角看 DFS

4.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(V+E))，单阶段总复杂度就是 (O(VE))。由于 (V \ge 1)，那点 BFS 开销被主项吸收，通常直接记作 (O(VE))。

这就是“单阶段 O(VE)”的完整来源。它不是一个粗略估计，而是一个摊还分析：成功路径的代价按路径长度算，失败代价按边的数量算，两边都没有漏掉。

5. 把三段拼起来：O(V²E) 的完整证明链

5.1 总时间怎么加总

把前两节的结果放到同一个式子里，就是：

[ \sum_{\text{阶段}} \left( O(V+E) + 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; }; vector<Edge> 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); queue<int> 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 long，INF初始化成足够大的数。如果INF小于真实最大流，一次 DFS 可能只推送很小流量，间接增加增广次数。虽然理论上复杂度上界没变，但常数会变得非常难看。

6.3 什么时候会真的慢

理论上，确实可以构造出让 Dinic 跑满 (V) 个阶段、每个阶段几乎遍历全图的例子，此时复杂度逼近 (O(V^2E))。这通常需要精心设计分层结构和容量分布，不是随便一个随机图都能达到。

实践中，Dinic 在绝大多数图上跑的阶段数都远小于 (V)，尤其是边容量不太极端的时候。但作为算法使用者，不能因为“平时快”就忽略证明。遇到构造卡数据的题目，知道复杂度上界能帮你判断要不要换算法，或者至少先怀疑是不是板子细节破坏了摊还。

6.4 单位容量图上的额外优势

如果图上每条边的容量都是 1，单位容量图会有更强结论，阶段数可以压到 (O(\sqrt V)) 这个量级。最典型的应用是二分图最大匹配：把源点连左部点、左部点连右部点、右部点连汇点，所有边容量为 1，Dinic 的行为就和 Hopcroft-Karp 算法非常接近，实际表现远好于一般网络流。

这也是为什么竞赛里有人说“Dinic 跑二分图匹配很快”。它不是玄学，而是特殊容量结构让阶段数的上界变得更紧。理解了这个，你就知道什么时候可以放心裸奔 Dinic，什么时候该考虑更专门的算法。

7. 最后分享两个我实际写板子时的习惯

7.1 用对拍验证正确性，也验证复杂度

我调试 Dinic 时，会先在随机小图和朴素增广路算法对拍，确认最大流结果一致。如果偶尔出现某张图跑得特别慢，我不会立刻怀疑复杂度结论，而是先查当前弧有没有重置、反向边下标对不对、BFS 是否严格判了剩余容量。经验告诉我，绝大多数“Dinic 被卡”其实是板子被卡，不是算法被卡。

7.2 把证明要点写成注释

我的板子里通常会留三行注释：阶段数 O(V) 来自距离严格递增；单阶段 O(VE) 来自失败边只扫一次加成功增广不超过 E；最终 O(V²E)。这样过几个月再回头看，不用重新推一遍也能马上想起每个优化到底在保护哪个上界。复杂度证明看起来绕，但它不是刁钻题，而是告诉你哪些优化动不得。理解了这条链之后，Dinic 才真正变成一个可以改的算法，而不是一段不能碰的模板。