最大流 学习笔记

搬运自 OI WIKI

概述

网络流基本概念参见 网络流基础。

令 $G=(V,E)$ 是一个有源汇点的网络，我们希望在 $G$ 上指定合适的流 $f$，以最大化整个网络的流量 $|f|$（即 ${\sum }_{x\in V}f(s,x)-{\sum }_{x\in V}f(x,s)$），这一问题被称作最大流问题（Maximum flow problem）。

策略 1：Ford–Fulkerson 增广

Ford–Fulkerson 增广是计算最大流的一类算法的总称。该方法运用贪心的思想，通过寻找增广路来更新并求解最大流。

概述

给定网络 $G$ 及 $G$ 上的流 $f$，我们做如下定义。

对于边 $(u,v)$，我们将其容量与流量之差称为剩余容量 $c_f(u,v)$（Residual Capacity），即 $c_f(u,v)=c(u,v)-f(u,v)$。

我们将 $G$ 中所有结点和剩余容量大于 $0$ 的边构成的子图称为残量网络 $G_f$（Residual Network），即 $G_f=(V,E_f)$，其中 $E_f=\left\{(u,v)\mid c_f(u,v)>0\right\}$。

WARNING

正如我们马上要提到的，流量可能是负值，因此，$E_f$ 的边有可能并不在 $E$ 中。引入增广的概念后，下文将具体解释这一点。

我们将 $G_f$ 上一条从源点 $s$ 到汇点 $t$ 的路径称为增广路（Augmenting Path）。对于一条增广路，我们给每一条边 $(u,v)$ 都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广（Augment）。由此，最大流的求解可以被视为若干次增广分别得到的流的叠加。

此外，在 Ford–Fulkerson 增广的过程中，对于每条边 $(u,v)$，我们都新建一条反向边 $(v,u)$。我们约定 $f(u,v)=-f(v,u)$，这一性质可以通过在每次增广时引入退流操作来保证，即 $f(u,v)$ 增加时 $f(v,u)$ 应当减少同等的量。

TIP

在最大流算法的代码实现中，我们往往需要支持快速访问反向边的操作。在邻接矩阵中，这一操作是 毫无难度的（$g_{u,v}\leftrightarrow g_{v,u}$）。但主流的实现是更加优秀的链式前向星。其中，一个常用的技巧是，我们令边从偶数（通常为 $0$）开始编号，并在加边时总是紧接着加入其反向边使得它们的编号相邻。由此，我们可以令编号为 $i$ 的边和编号为 $i\oplus 1$ 的边始终保持互为反向边的关系。

初次接触这一方法的读者可能察觉到一个违反直觉的情形——反向边的流量 $f(v,u)$ 可能是一个负值。实际上我们可以注意到，在 Ford–Fulkerson 增广的过程中，真正有意义的是剩余容量 $c_f$，而 $f(v,u)$ 的绝对值是无关紧要的，我们可以将反向边流量的减少视为反向边剩余容量 $c_f(v,u)$ 的增加——这也与退流的意义相吻合——反向边剩余容量的增加意味着我们接下来可能通过走反向边来和原先正向的增广抵消，代表一种「反悔」的操作。

以下案例有可能帮助你理解这一过程。假设 $G$ 是一个单位容量的网络，我们考虑以下过程：

• $G$ 上有多条增广路，其中，我们选择进行一次先后经过 $u,v$ 的增广（如左图所示），流量增加 $1$。
• 我们注意到，如果进行中图上的增广，这个局部的最大流量不是 $1$ 而是 $2$。但由于指向 $u$ 的边和从 $v$ 出发的边在第一次增广中耗尽了容量，此时我们无法进行中图上的增广。这意味着我们当前的流是不够优的，但局部可能已经没有其他（只经过原图中的边而不经过反向边的）增广路了。
• 现在引入退流操作。第一次增广后，退流意味着 $c_f(v,u)$ 增加了 $1$ 剩余容量，即相当于新增 $(v,u)$ 这条边，因此我们可以再进行一次先后经过 $p,v,u,q$ 的增广（如右图橙色路径所示）。无向边 $(u,v)$ 上的流量在两次增广中抵消，我们惊奇地发现两次增广叠加得到的结果实际上和中图是等价的。

以上案例告诉我们，退流操作带来的「抵消」效果使得我们无需担心我们按照「错误」的顺序选择了增广路。

容易发现，只要 $G_f$ 上存在增广路，那么对其增广就可以令总流量增加；否则说明总流量已经达到最大可能值，求解过程完成。这就是 Ford–Fulkerson 增广的过程。

最大流最小割定理

我们大致了解了 Ford–Fulkerson 增广的思想，可是如何证明这一方法的正确性呢？为什么增广结束后的流 $f$ 是一个最大流？

实际上，Ford–Fulkerson 增广的正确性和最大流最小割定理（The Maxflow-Mincut Theorem）等价。这一定理指出，对于任意网络 $G=(V,E)$，其上的最大流 $f$ 和最小割 $\{S,T\}$ 总是满足 $|f|=||S,T||$。

为了证明最大流最小割定理，我们先从一个引理出发：对于网络 $G=(V,E)$，任取一个流 $f$ 和一个割 $\{S,T\}$，总是有 $|f|\le ||S,T||$，其中等号成立当且仅当 $\{(u,v)|u\in S,v\in T\}$ 的所有边均满流，且 $\{(u,v)|u\in T,v\in S\}$ 的所有边均空流。

引理的证明：

$$\begin{array}{rl}|f|& =f(s)\\ & =\sum _{u\in S}f(u)\\ & =\sum _{u\in S}\left(\sum _{v\in V}f(u,v)-\sum _{v\in V}f(v,u)\right)\\ & =\sum _{u\in S}\left(\sum _{v\in T}f(u,v)+\sum _{v\in S}f(u,v)-\sum _{v\in T}f(v,u)-\sum _{v\in S}f(v,u)\right)\\ & =\sum _{u\in S}\left(\sum _{v\in T}f(u,v)-\sum _{v\in T}f(v,u)\right)+\sum _{u\in S}\sum _{v\in S}f(u,v)-\sum _{u\in S}\sum _{v\in S}f(v,u)\\ & =\sum _{u\in S}\left(\sum _{v\in T}f(u,v)-\sum _{v\in T}f(v,u)\right)\\ & \le \sum _{u\in S}\sum _{v\in T}f(u,v)\\ & \le \sum _{u\in S}\sum _{v\in T}c(u,v)\\ & =||S,T||\end{array}$$

为了取等，第一个不等号需要 $\{(u,v)\mid u\in T,v\in S\}$ 的所有边均空流，第二个不等号需要 $\{(u,v)\mid u\in S,v\in T\}$ 的所有边均满流。原引理得证。

---

那么，对于任意网络，以上取等条件是否总是能被满足呢？如果答案是肯定的，则最大流最小割定理得证。以下我们尝试证明。

最大流最小割定理的证明：

假设某一轮增广后，我们得到流 $f$ 使得 $G_f$ 上不存在增广路，即 $G_f$ 上不存在 $s$ 到 $t$ 的路径。此时我们记从 $s$ 出发可以到达的结点组成的点集为 $S$，并记 $T=V\setminus S$。

显然，$\{S,T\}$ 是 $G_f$ 的一个割，且 $||S,T||={\sum }_{u\in S}{\sum }_{v\in T}{c}_f(u,v)=0$。由于剩余容量是非负的，这也意味着对于任意 $u\in S,v\in T,(u,v)\in E_f$，均有 $c_f(u,v)=0$。以下我们将这些边分为存在于原图中的边和反向边两种情况讨论：

• $(u,v)\in E$：此时，$c_f(u,v)=c(u,v)-f(u,v)=0$，因此有 $c(u,v)=f(u,v)$，即 $\{(u,v)\mid u\in S,v\in T\}$ 的所有边均满流；
• $(v,u)\in E$：此时，$c_f(u,v)=c(u,v)-f(u,v)=0-f(u,v)=f(v,u)=0$，即 $\{(v,u)\mid u\in S,v\in T\}$ 的所有边均空流。

因此，增广停止后，上述流 $f$ 满足取等条件。根据引理指出的大小关系，自然地，$f$ 是 $G$ 的一个最大流，$\{S,T\}$ 是 $G$ 的一个最小割。

---

容易看出，Kőnig 定理是最大流最小割定理的特殊情形。实际上，它们都和线性规划中的对偶有关。

时间复杂度分析

在整数流量的网络 $G=(V,E)$ 上，平凡地，我们假设每次增广的流量都是整数，则 Ford–Fulkerson 增广的时间复杂度的一个上界是 $O(|E||f|)$，其中 $f$ 是 $G$ 上的最大流。这是因为单轮增广的时间复杂度是 $O(|E|)$，而增广会导致总流量增加，故增广轮数不可能超过 $|f|$。

对于 Ford–Fulkerson 增广的不同实现，时间复杂度也各不相同。其中较主流的实现有 Edmonds–Karp, Dinic, SAP, ISAP 等算法，我们将在下文中分别介绍。

Edmonds–Karp 算法

算法思想

如何在 $G_f$ 中寻找增广路呢？当我们考虑 Ford–Fulkerson 增广的具体实现时，最自然的方案就是使用 BFS。此时，Ford–Fulkerson 增广表现为 Edmonds–Karp 算法。其具体流程如下：

• 如果在 $G_f$ 上我们可以从 $s$ 出发 BFS 到 $t$，则我们找到了新的增广路。

• 对于增广路 $p$，我们计算出 $p$ 经过的边的剩余容量的最小值 $\Delta ={\min }_{(u,v)\in p}{c}_f(u,v)$。我们给 $p$ 上的每条边都加上 $\Delta$ 流量，并给它们的反向边都退掉 $\Delta$ 流量，令最大流增加了 $\Delta$。

• 因为我们修改了流量，所以我们得到新的 $G_f$，我们在新的 $G_f$ 上重复上述过程，直至增广路不存在，则流量不再增加。

以上算法即 Edmonds–Karp 算法。

时间复杂度分析

接下来让我们尝试分析 Edmonds–Karp 算法的时间复杂度。

显然，单轮 BFS 增广的时间复杂度是 $O(|E|)$。

增广总轮数的上界是 $O(|V||E|)$。这一论断在网络资料中常被伪证（或被含糊其辞略过）。以下我们尝试给出一个较正式的证明。

增广总轮数的上界的证明

首先，我们引入一个引理——最短路非递减引理。具体地，我们记 $d_f(u)$ 为 $G_f$ 上结点 $u$ 到源点 $s$ 的距离（即最短路长度，下同）。对于某一轮增广，我们用 $f$ 和 $f^{\prime }$ 分别表示增广前的流和增广后的流，我们断言，对于任意结点 $u$，增广总是使得 $d_{f^{\prime }}(u)\ge d_f(u)$。接下来将证明这一引理。

---

不妨称增广路上剩余容量最小的边是饱和边（存在多条边同时最小则取任一）。如果一条有向边 $(u,v)$ 被选为饱和边，增广会清空其剩余容量导致饱和边的消失，并且退流导致反向边的新增（如果原先反向边不存在），即 $(u,v)\notin E_{f^{\prime }}$ 且 $(v,u)\in E_{f^{\prime }}$。以上分析使我们知道，对于无向边 $(u,v)$，其被增广的两种方向总是交替出现。

在 $G_f$ 上沿 $(u,v)$ 增广时，$d_f(u)+1=d_f(v)$，此后残量网络变为 $G_{f^{\prime }}$。在 $G_{f^{\prime }}$ 上沿 $(v,u)$ 增广时，$d_{f^{\prime }}(v)+1=d_{f^{\prime }}(u)$。根据最短路非递减引理又有 $d_{f^{\prime }}(v)\ge d_f(v)$，我们连接所有式子，得到 $d_{f^{\prime }}(u)\ge d_f(u)+2$。换言之，如果有向边 $(u,v)$ 被选为饱和边，那么与其上一次被选为饱和边时相比，$u$ 到 $s$ 的距离至少增加 $2$。

$s$ 到任意结点的距离不可能超过 $|V|$，结合上述性质，我们发现每条边被选为饱和边的次数是 $O(|V|)$ 的，与边数相乘后得到增广总轮数的上界 $O(|V||E|)$。

接下来我们证明最短路非递减引理，即 $d_{f^{\prime }}(u)\ge d_f(u)$。这一证明并不难，但可能稍显绕口，读者可以停下来认真思考片刻。

最短路非递减引理的证明

考虑反证。对于某一轮增广，我们假设存在若干结点，它们在该轮增广后到 $s$ 的距离较增广前减小。我们记 $v$ 为其中到 $s$ 的距离最小的一者（即 $v=\arg {\min }_{x\in V,d_{f^{\prime }}(x)<d_f(x)}{d}_{f^{\prime }}(x)$）。注意，根据反证假设，此时 $d_{f^{\prime }}(v)<d_f(v)$ 是已知条件。

• 在 $G_{f^{\prime }}$ 中 $s$ 到 $v$ 的最短路上，我们记 $u$ 是 $v$ 的上一个结点，即 $d_{f^{\prime }}(u)+1=d_{f^{\prime }}(v)$。

• 为了不让 $u$ 破坏 $v$ 的「距离最小」这一性质，$u$ 必须满足 $d_{f^{\prime }}(u)\ge d_f(u)$。

• 对于上式，我们令不等号两侧同加，得 $d_{f^{\prime }}(v)\ge d_f(u)+1$。根据反证假设进行放缩，我们得到 $d_f(v)>d_f(u)+1$。

• 然后我们尝试讨论 $(u,v)$ 上的增广方向。

  • 假设有向边 $(u,v)\in E_f$。根据 BFS「广度优先」的性质，我们有 $d_f(u)+1\ge d_f(v)$。该式与放缩结果冲突，导出矛盾。

    • 假设有向边 $(u,v)\notin E_f$。根据 $u$ 的定义我们已知 $(u,v)\in E_{f^{\prime }}$，因此这条边的存在必须是当前轮次的增广经过了 $(v,u)$ 并退流产生反向边的结果，也即 $d_f(v)+1=d_f(u)$。该式与放缩结果冲突，导出矛盾。

• 由于 $(u,v)$ 沿任何方向增广都会导出矛盾，我们知道反证假设不成立，最短路非递减引理得证。

---

将单轮 BFS 增广的复杂度与增广轮数的上界相乘，我们得到 Edmonds–Karp 算法的时间复杂度是 $O(|V||E{|}^2)$

Dinic 算法

NOTE

由于其对于常见建模情况下的网络具有优秀的时间复杂度，使其成为现阶段相当重要的工具算法

算法思想

考虑在增广前先对 $G_f$ 做 BFS 分层，即根据结点 $u$ 到源点 $s$ 的距离 $d(u)$ 把结点分成若干层。令经过 $u$ 的流量只能流向下一层的结点 $v$，即删除 $u$ 向层数标号相等或更小的结点的出边，我们称 $G_f$ 剩下的部分为层次图（Level Graph）。形式化地，我们称 $G_L=(V,E_L)$ 是 $G_f=(V,E_f)$ 的层次图，其中 $E_L=\left\{(u,v)\mid (u,v)\in E_f,d(u)+1=d(v)\right\}$。

如果我们在层次图 $G_L$ 上找到一个最大的增广流 $f_b$，使得仅在 $G_L$ 上是不可能找出更大的增广流的，则我们称 $f_b$ 是 $G_L$ 的阻塞流（Blocking Flow）。

WARNING

尽管在上文中我们仅在单条增广路上定义了增广/增广流，广义地，「增广」一词不仅可以用于单条路径上的增广流，也可以用于若干增广流的并——后者才是我们定义阻塞流时使用的意义。

定义层次图和阻塞流后，Dinic 算法的流程如下。

1. 在 $G_f$ 上 BFS 出层次图 $G_L$。
2. 在 $G_L$ 上 DFS 出阻塞流 $f_b$。
3. 将 $f_b$ 并到原先的流 $f$ 中，即 $f\leftarrow f+f_b$。
4. 重复以上过程直到不存在从 $s$ 到 $t$ 的路径。

此时的 $f$ 即为最大流。

在分析这一算法的复杂度之前，我们需要特别说明「在 $G_L$ 上 DFS 出阻塞流 $f_b$」的过程。尽管 BFS 层次图对于本页面的读者应当是 trivial 的，但 DFS 阻塞流的过程则稍需技巧——我们需要引入当前弧优化。

注意到在 $G_L$ 上 DFS 的过程中，如果结点 $u$ 同时具有大量入边和出边，并且 $u$ 每次接受来自入边的流量时都遍历出边表来决定将流量传递给哪条出边，则 $u$ 这个局部的时间复杂度最坏可达 $O(|E{|}^2)$。为避免这一缺陷，如果某一时刻我们已经知道边 $(u,v)$ 已经增广到极限（边 $(u,v)$ 已无剩余容量或 $v$ 的后侧已增广至阻塞），则 $u$ 的流量没有必要再尝试流向出边 $(u,v)$。据此，对于每个结点 $u$，我们维护 $u$ 的出边表中第一条还有必要尝试的出边。习惯上，我们称维护的这个指针为当前弧，称这个做法为当前弧优化。

多路增广

• 多路增广是 Dinic 算法的一个常数优化——如果我们在层次图上找到了一条从 $s$ 到 $t$ 的增广路 $p$，则接下来我们未必需要重新从 $s$ 出发找下一条增广路，而可能从 $p$ 上最后一个仍有剩余容量的位置出发寻找一条岔路进行增广。考虑到其与回溯形式的一致性，这一优化在 DFS 的代码实现中也是自然的。

WARNING

可能是由于大量网络资料的错误表述引发以讹传讹的情形，相当数量的选手喜欢将当前弧优化和多路增广并列称为 Dinic 算法的两种优化。实际上，当前弧优化是用于保证 Dinic 时间复杂度正确性的一部分，而多路增广只是一个不影响复杂度的常数优化。

时间复杂度分析

应用当前弧优化后，对 Dinic 算法的时间复杂度分析如下。

首先，我们尝试证明单轮增广中 DFS 求阻塞流的时间复杂度是 $O(|V||E|)$。

单轮增广的时间复杂度的证明

• 考虑阻塞流 $f_b$ 中的每条增广路，它们都是在 $G_L$ 上每次沿当前弧跳转而得到的结果，其中每条增广路经历的跳转次数不可能多于 $|V|$。
• 每找到一条增广路就有一条饱和边消失（剩余容量清零）。考虑阻塞流 $f_b$ 中的每条增广路，我们将被它们清零的饱和边形成的边集记作 $E_1$。考虑到 $G_L$ 分层的性质，饱和边消失后其反向边不可能在同一轮增广内被其他增广路经过，因此，$E_1$ 是 $E_L$ 的子集。
• 此外，对于沿当前弧跳转但由于某个位置阻塞所以没有成功得到增广路的情形，我们将这些不完整的路径上的最后一条边形成的边集记作 $E_2$。$E_2$ 的成员不饱和，所以 $E_1$ 与 $E_2$ 不交，且 $E_1\cup E_2$ 仍是 $E_L$ 的子集。
• 由于 $E_1\cup E_2$ 的每个成员都没有花费超过 $|V|$ 次跳转（且在使用多路增广优化后一些跳转将被重复计数），因此，综上所述，DFS 过程中的总跳转次数不可能多于 $|V||E_L|$。

常见伪证一则

• 对于每个结点，我们维护下一条可以增广的边，而当前弧最多变化 $|E|$ 次，从而单轮增广的最坏时间复杂度为 $O(|V||E|)$。
• 问题在于
  • 「当前弧最多变化 $|E|$ 次」并不能推得「每个结点最多访问其出边 $|E|$ 次」。这是因为，访问当前弧并不一定耗尽上面的剩余容量，结点 $u$ 可能多次访问同一条当前弧。

注意到层次图的层数显然不可能超过 $|V|$，如果我们可以证明层次图的层数在增广过程中严格单增，则 Dinic 算法的增广轮数是 $O(|V|)$ 的。接下来我们尝试证明这一结论。

层次图层数单调性的证明

我们需要引入预流推进类算法（另一类最大流算法）中的一个概念——高度标号。

为了更方便地结合高度标号表述我们的证明，在证明过程中，我们令 $d_f(u)$ 为 $G_f$ 上结点 $u$ 到 汇点 $t$ 的距离，从 汇点 而非源点出发进行分层（这并没有本质上的区别）。

对于某一轮增广，我们用 $f$ 和 $f^{\prime }$ 分别表示增广前的流和增广后的流。在该轮增广中求解并加入阻塞流后，记层次图由 $G_L=(V,E_L)$ 变为 $G_L^{\prime }=(V,E_L^{\prime })$。

我们给高度标号一个不严格的临时定义——在网络 $G=(V,E)$ 上，令 $h$ 是点集 $V$ 到整数集 $N$ 上的函数，$h$ 是 $G$ 上合法的高度标号当且仅当 $h(u)\le h(v)+1$ 对于 $(u,v)\in E$ 恒成立。

考察所有 $E_{f^{\prime }}$ 的成员 $(u,v)$，我们发现 $(u,v)\in E_{f^{\prime }}$ 的原因是以下二者之一。

• $(u,v)\in E_f$，且剩余容量在该轮增广过程中未耗尽——根据最短路的定义，此时我们有 $d_f(u)\le d_f(v)+1$
• $(u,v)\notin E_f$，但在该轮增广过程中阻塞流经过 $(v,u)$ 并退流产生反向边——根据层次图和阻塞流的定义，此时我们有 $d_f(u)+1=d_f(v)$。

以上观察让我们得出一个结论——$d_f$ 在 $G_{f^{\prime }}$ 上是一个合法的高度标号。当然，在 $G_{f^{\prime }}$ 的子图 $G_L^{\prime }$ 上也是。

现在，对于一条 $G_L^{\prime }$ 上的增广路 $p=(s,\dots ,u,v,\dots ,t)$，按照 $p$ 上结点的反序（从 $t$ 到 $s$ 的顺序）考虑从空路径开始每次添加一个结点的过程。

• 假设结点 $v$ 已加入，结点 $u$ 正在加入，我们发现，加入结点 $u$ 后，根据层次图的定义，$d_{f^{\prime }}(u)$ 的值较 $d_{f^{\prime }}(v)$ 增加 $1$
• 与此同时，由于 $d_f$ 是 $G_L^{\prime }$ 上的高度标号，$d_f(u)$ 的值既可能较 $d_f(v)$ 增加 $1$，也可能保持不变或减少。因此，在整条路径被添加完成后，我们得到 $d_{f^{\prime }}(s)\ge d_f(s)$，其中取等的充要条件是 $d_f(u)=d_f(v)+1$ 对于 $(u,v)\in p$ 恒成立。
• 如果该不等式不能取等，则有 $d_{f^{\prime }}(s)>d_f(s)$——即我们想要的结论「层次图的层数在增广过程中严格单增」。
• 以下我们尝试证明该不等式不能取等

考虑反证，我们假设 $d_{f^{\prime }}(s)=d_f(s)$ 成立，并尝试导出矛盾。

现在我们断言，在 $G_L^{\prime }$ 上，$p$ 至少包含一条边 $(u,v)$ 满足 $(u,v)$ 在 $G_L$ 上不存在。如果没有这样的边，考虑到 $d_f(s)=d_{f^{\prime }}(s)$，结合层次图和阻塞流的定义，$G_L$ 上的增广应尚未完成。为了不产生以上矛盾，我们的断言只好是正确的。

令 $(u,v)$ 是满足断言条件的那条边，其满足断言的原因只能是以下二者之一。

• $(u,v)\in E_f$ 但 $d_f(u)\le d_f(v)+1$ 未取等

  • 故根据层次图的定义可知 $(u,v)\notin E_L$，并在增广后新一轮重分层中被加入到 $E_L^{\prime }$ 中；

• $(u,v)\notin E_f$

  • 这意味着 $(u,v)$ 这条边的产生是当前轮次增广中阻塞流经过 $(v,u)$ 并退流产生反向边的结果，也即 $d_f(u)=d_f(v)-1$。

由于我们无论以何种方式满足断言均得到 $d_f(u)\ne d_f(v)+1$，也即 $d_{f^{\prime }}(s)\ge d_f(s)$ 取等的充要条件无法被满足，这与反证假设 $d_{f^{\prime }}(s)=d_f(s)$ 冲突，原命题得证。

---

常见伪证另一则

• 考虑反证。假设层次图的层数在一轮增广结束后较原先相等，则层次图上应仍存在至少一条从 $s$ 到 $t$ 的增广路满足相邻两点间的层数差为 $1$。这条增广路未被增广说明该轮增广尚未结束。为了不产生上述矛盾，原命题成立。
• 问题在于
  • 「一轮增广结束后新的层次图上 $s$-$t$ 最短路较原先相等」并不能推得「旧的层次图上该轮增广尚未结束」
  • 这是因为，没有理由表明两张层次图的边集相同，新的层次图上的 $s$-$t$ 最短路有可能经过旧的层次图上不存在的边

将单轮增广的时间复杂度 $O(|V||E|)$ 与增广轮数 $O(|V|)$ 相乘，Dinic 算法的时间复杂度是 $O(|V{|}^2|E|)$。

---

如果需要令 Dinic 算法的实际运行时间接近其理论上界，我们需要构造有特殊性质的网络作为输入。

由于在算法竞赛实践中，对于网络流知识相关的考察常侧重于将原问题建模为网络流问题的技巧。此时，我们的建模通常不包含令 Dinic 算法执行缓慢的特殊性质；恰恰相反，Dinic 算法在大部分图上效率非常优秀。

因此，网络流问题的数据范围通常较大，「将 $|V|,|E|$ 的值代入 $|V{|}^2|E|$ 以估计运行时间」这一方式并不适用。实际上，进行准确的估计需要选手对 Dinic 算法的实际效率有一定的经验，读者可以多加练习。

特殊情形下的时间复杂度分析

在一些性质良好的图上，Dinic 算法有更好的时间复杂度。

对于网络 $G=(V,E)$，如果其所有边容量均为 $1$，即 $c(u,v)\in \{0,1\}$ 对于 $(u,v)\in E$ 恒成立，则我们称 $G$ 是单位容量（Unit Capacity）的。

在单位容量的网络中，Dinic 算法的单轮增广的时间复杂度为 $O(|E|)$。

证明

• 这是因为，每次增广都会导致增广路上的所有边均饱和并消失，故单轮增广中每条边只能被增广一次。

在单位容量的网络中，Dinic 算法的增广轮数是 $O(|E{|}^{\frac{1}{2}})$ 的。

证明

• 以源点 $s$ 为中心分层，记 $d_f(u)$ 为 $G_f$ 上结点 $u$ 到源点 $s$ 的距离。另外，我们定义将点集 $\left\{u\mid u\in V,d_f(u)=k\right\}$ 定义为编号为 $k$ 的层次 $D_k$，并记 $S_k={\cup }_{i\le k}{D}_i$。

• 假设我们已经进行了 $|E{|}^{\frac{1}{2}}$ 轮增广。根据鸽巢原理，至少存在一个 $k$ 满足边集 $\left\{(u,v)\mid u\in D_k,v\in D_{k+1},(u,v)\in E_f\right\}$ 的大小不超过 $\frac{|E|}{|E{|}^{\frac{1}{2}}}\approx |E{|}^{\frac{1}{2}}$。

• 显然，$\{S_k,V-S_k\}$ 是 $G_f$ 上的 $s$-$t$ 割，且其割容量不超过 $|E{|}^{\frac{1}{2}}$。

• 根据最大流最小割定理，$G_f$ 上的最大流不超过 $|E{|}^{\frac{1}{2}}$，也即 $G_f$ 上最多还能执行 $|E{|}^{\frac{1}{2}}$ 轮增广。

• 因此，总增广轮数是 $O(|E{|}^{\frac{1}{2}})$ 的。

在单位容量的网络中，Dinic 算法的增广轮数是 $O(|V{|}^{\frac{2}{3}})$ 的。

证明

• 假设我们已经进行了 $2|V{|}^{\frac{2}{3}}$ 轮增广。由于至多有半数的（$|V{|}^{\frac{2}{3}}$ 个）层次包含多于 $|V{|}^{\frac{1}{3}}$ 个点，故无论我们如何分配所有层次的大小，至少存在一个 $k$ 满足相邻两个层次同时包含不多于 $|V{|}^{\frac{1}{3}}$ 个点，即 $|D_k|\le |V{|}^{\frac{1}{3}}$ 且 $|D_{k+1}|\le |V{|}^{\frac{1}{3}}$。
• 为最大化 $D_k$ 和 $D_{k+1}$ 之间的边数，我们假定这是一个完全二分图，此时边集 $\left\{(u,v)\mid u\in D_k,v\in D_{k+1},(u,v)\in E_f\right\}$ 的大小不超过 $|V{|}^{\frac{2}{3}}$。
• 显然，$\{S_k,V-S_k\}$ 是 $G_f$ 上的 $s$-$t$ 割，且其割容量不超过 $|V{|}^{\frac{2}{3}}$。
• 根据最大流最小割定理，$G_f$ 上的最大流不超过 $|V{|}^{\frac{2}{3}}$，也即 $G_f$ 上最多还能执行 $|V{|}^{\frac{2}{3}}$ 轮增广。
• 因此，总增广轮数是 $O(|V{|}^{\frac{2}{3}})$ 的。

在单位容量的网络中，如果除源汇点外每个结点 $u$ 都满足 ${deg}_{in}(u)=1$ 或 ${deg}_{out}(u)=1$，则 Dinic 算法的增广轮数是 $O(|V{|}^{\frac{1}{2}})$ 的。其中，${deg}_{in}(u)$ 和 ${deg}_{out}(u)$ 分别代表结点 $u$ 的入度和出度。

证明

• 我们引入以下引理——对于这一形式的网络，其上的任意流总是可以分解成若干条单位流量的、点不交 的增广路。

• 假设我们已经进行了 $|V{|}^{\frac{1}{2}}$ 轮增广。根据层次图的定义，此时任意新的增广路的长度至少为 $|V{|}^{\frac{1}{2}}$。

• 考虑 $G_f$ 上的最大流的增广路分解，我们得到的增广路的数量不能多于 $\frac{|V|}{|V{|}^{\frac{1}{2}}}\approx |V{|}^{\frac{1}{2}}$，这意味着 $G_f$ 上最多还能执行 $|V{|}^{\frac{1}{2}}$ 轮增广。

• 因此，总增广轮数是 $O(|V{|}^{\frac{1}{2}})$ 的。

综上，我们得出一些重要结论：

• 在单位容量的网络上，Dinic 算法的总时间复杂度是 $O(|E|\min (|E{|}^{\frac{1}{2}},|V{|}^{\frac{2}{3}}))$。
• 在单位容量的网络上，如果除源汇点外每个结点 $u$ 都满足 ${deg}_{in}(u)=1$ 或 ${deg}_{out}(u)=1$，Dinic 算法的总时间复杂度是 $O(|E||V{|}^{\frac{1}{2}})$。对于二分图最大匹配问题，我们常使用 Hopcroft–Karp 算法解决，而这一算法实际上是 Dinic 算法在满足上述度数限制的单位容量网络上的特例。