Maximum Flow

免责声明：code太难写了，本章就不提供code了，各位自行GPT吧（

基本概念阐述

问题阐述

• 输入：一个有向有权图 $G=(V,E)$ ，源节点 $s$ ，汇点 $t$​
• 目标：从 $s$ 发送尽可能多的水到 $t$​
• 约束：
  • 流要小于管道容量

流网络和流

• 流网络

  • $G=(V,E)$​ 是一个有向有权图
    • $|E|\ge |V|-1$
  • 图中每一条边 $(u,v)\in E$ 有一个非负的容量值 $c(u,v)\ge 0$
    • 若 $(u,v)\notin E$ ，则定义 $c(u,v)=0$
  • 源节点 $s$ ，汇点 $t$

• 流 $flow$

  • 在一个流网络 $G=(V,E)$ 中，设容量函数为 $c$ ，源节点 $s$ ，汇点 $t$

  • $G$ 中的流为一个实值函数 $f:V \times V \to R$ ，满足以下两条性质​：

    • 容量限制：对于所有的节点，$0\le f(u,v)\le c(u,v)$ ​
    • 流量守恒：对于除源节点、汇点外（$V-\{s,t\}$）的所有节点，$\sum_{v \in V}f(v,u)=\sum_{v \in V} f(u,v)$​
      • 即流入 $u$ 的总流量等于从 $u$​ 流出的总流量
      • 前后两个 $v$ 一般是不同的，所以我更倾向写成 $\sum_{v \in V}f(v,u)=\sum_{v' \in V} f(u,v')$
      • 当 $(u,v)\notin E$ ，则 $f(u,v)=0$​

  • 一个流的值 $|f|$ 定义为：

    $$|f|=\sum_{v\in V}f(s,v)-\sum_{v \in V}f(v,s)$$

    • 表示从源结点流入该节点的总流量减去流入源结点的总流量。
    • 一般而言，没有流入源节点的流，即第二项的值为 $0$​ ，所以也可以写成：

  $$|f|=\sum_{v\in V}f(s,v)$$

残存网络 $Residual\ Graph$​

• 残存边 $(u,v)$ ，残存容量 $c_f=c(u,v)-f(u,v)$​​​
• 回流边 $(v,u)$ ，回流值大小 $c_{f'}=f'(v,u)=f(u,v)$ ——在 $Ford-Fulkerson$ 方法里会用到
  • $c_{f'}=\sum f'(v,u)$ ，也即合并 $Merge$ 操作，后面会给出证明

增广路径 $Augmenting\ paths$

• 增广路径 $p$ 是从源节点 $s$ 到汇点 $t$ 的一条简单路径
• 路径 $p$ 的瓶颈容量 $c_f(p)=min\{c_f(u,v):(u,v)\in p\}$​

切割

切割，字面意思，就是把图切割成 $n$ 份。在本章中，我们主要讨论的是 $\mathcal{S-T}\ cut$ ，即把图切割成两份。

• $\mathcal{S-T}\ cut$

  • 将节点集合 $V$ 切割成两个子集：$\mathcal{S}$ 和 $\mathcal{T}$​

    • $\mathcal{S} \cup \mathcal{T}=V$ ，$\mathcal{S} \cap \mathcal{T}=\emptyset$
    • $s \in \mathcal{S}$ ， $t \in \mathcal{T}$​

  • $\mathcal{S}$ 和 $\mathcal{T}$ 的二元组 $(\mathcal{S},\mathcal{S})$ 被称为 $\mathcal{S-T}\ cut$​

  • 定义 $\mathcal{S-T}$ 的容量为离开集合 $\mathcal{S}$​ 的边的权重之和，如下：

    $$c(\mathcal{S},\mathcal{T})=\sum_{u \in \mathcal{S}}\sum_{v \in \mathcal{T}}c(u,v)$$

    • 例如下图的 $c(\mathcal{S},\mathcal{T})=6$

  • 定义切割的净流量 $f(\mathcal{S},\mathcal{T})$ 如下：

    $$f(\mathcal{S},\mathcal{T})=\sum_{u \in \mathcal{S}}\sum_{v \in \mathcal{T}}f(u,v)-\sum_{u \in \mathcal{S}}\sum_{v \in \mathcal{T}}f(v,u)$$

    • 例如下图的 $f(\mathcal{S},\mathcal{T})=f(v_1,v_3)+f(v_1,v_4)+f(v_2,v_4)-f(v_4,s)=2+2+2-4=2$

  • e.g.

  
  • 注意，$\mathcal{S-T}\ cut$ 不唯一
  

• 最小割 $Min-Cut$

  • 使容量最小化的切割被称为最小割 $Min-Cut$
  • e.g.
  

$Naive\ Algorithm$ 引入

Naive 不是一个人名，它的意思是天真的；幼稚的。这里应译为朴素算法

​ 这个算法是初步的算法，并不一定能找到最大流（只能找到阻塞流），只是大多数情况下可以找到最大流，但是这种方法很好理解，并且后面的更优的算法都是以此为基础进行优化的，所以我们先介绍这种算法。

算法实现步骤

• 创建一个残存图 $(residual\ graph)$ ，初始化残存容量
• $while$ 可以找到增广路径 :
  • 找一条增广路径
  • 找出增广路径中的瓶颈容量 $x$
  • 更新这条增广路径上每一条边，$c_f=c_f-x$ ，并删除饱和边

图示

• 初始化
  

• 第一轮循环

  • 随便用什么遍历方法找到一条从 $s$ 到 $t$​​​ 的增广路径，找到瓶颈容量，更新这条路径上的每一条边

    

  • 此时有两条边的余量为0，说明这两条管道已经饱和了，于是把余量为0的边删除

• 第二轮循环

  • 同样的操作

• 第三轮循环
  • 同样的操作

• 循环结束
  • 用原始图减去最终的残存图，即可得到流量图
  • 实际流量可以从源节点 $s$ 去进行计算

该简单算法局限性

该算法在寻找路径的时候，如果找到的路径是错误的，则最终找到的有可能不是最大流

阻塞流 $blocking\ flow$

• 如果从源节点 $s$ 到汇点 $t$ ，不能找到更多的流汇入，则该流是阻塞流
• 最大流是阻塞流

$Ford-Fulkerson$ 算法

​ 上面的简单算法一旦选择了 $bad\ path$ 后，不能修正，就只能找到阻塞流。

​ 而下面我们介绍的算法，则是以上面的算法为基础进行优化的，$Ford-Fulkerson$ 算法添加了回流这一步操作，假如选到了阻塞流，则可以进行回流修正，从而解决了问题。

图示

​ 我们以刚刚的基本算法的示例图来进行算法介绍

• 依旧进行初始化

• 第一轮循环

  • 这三步和之前的 $naive\ algorithm$​ 都是一样的，关键在于之后的一步
  
  - 在删除了饱和边之后，$Ford-Fulkerson\ Algorithm$ 增加了一步回流法：画出该增广路径的回流边，即从 $t$ 到 $s$​ 的流向。并且这些回流边在下一轮选择路径试仍然可以被选中。

  - 为什么可以这么做？这样做对算法的正确性有无影响？这里先介绍完算法，后文会给出正确性证明。
  

• 第二轮循环

  • 依旧如此，进行同样的操作
  
  - 此时我们注意到：在 $v_1 \to s$​ 这条路径，有两条回流边，此时我们很容易就会想到一个问题，这两条边，是否可以合并？ - 答案是肯定的，同样的，我们在算法正确性小节会给出证明 - 第二轮循环结束的图如下：

• 第三轮循环

  • 第三轮循环即是刚刚简单算法失败的地方，我们来看 $Ford-Fulkerson$​ 算法是如何纠正的
    • 此图很清晰地说明了回流边的作用——给后面的纠错预留操作空间

• 循环结束

  • 此时，图中没有从 $s$ 到 $t$​ 的路径了，于是算法终止。
  
  • 因此，我们可以得到流量图，且该图的 $Maximum\ Flow$ 为 $5$ 。
  

算法实现步骤

刚刚我们介绍了 $Naive\ Algorithm$ ，对于 $Ford-Fulkerson$ 算法的步骤，也只需添加一句话：

• 创建一个残存图 $(residual\ graph)$ ，初始化残存容量
• $while$ 可以找到增广路径 :
  • 找一条增广路径
  • 找出增广路径中的瓶颈容量 $x$
  • 更新这条增广路径上每一条边，$c_f=c_f-x$​​ ，并删除饱和边
  • ==添加该增广路径的回流边==

最坏时间复杂度分析

• $while$​​ 循环最坏情况

  ​ 不难看出，该图的最大流为 $200$ ，若选择路径时，非常"好运"地选择了 $s \to v_1 \to v_2 \to t$ 这条路径，则会发生一些 $amazing$ 的事情，即后面两张图。此时，循环就会进行 $200$ 遍，即进行 $Amount\ of\ MaxFlow$ 遍。

​ 以下给出证明：

​ 由于每一轮循环中，流量值至少增加 $1$ ，$Flowvalue$ 从 $0$ 开始增长到 $MaxFlow$

​ 所以，$Iterations \le Amount\ of\ MaxFlow$

​ 在这个例子中，$Iterations = Amount\ of\ MaxFlow$

​ 综上所述，循环的次数为：$O(f^*)$ ，其中 $f^*$ 代表最大流的大小。

• 寻找路径最坏情况

  ​ 假设有向图 $G$ 中有 $E$ 条边，$V$ 个结点，并且所有的结点都至少有一条相邻边，则 $E \ge \frac{V}{2}$

  ​ 所以如果使用 $bfs$ 或 $dfs$ ，在一个残存网络中找到一条路径的时间可以化为：$O(V+E')=O(E)$​

• 最坏时间复杂度

  ​ 综上所述，最坏时间复杂度为：$O(Ef^*)$​

*算法正确性证明

​ 在算法介绍中，我们得知了设置回流边的意义，现在，我们来探究为什么能设置回流边，以及我们对回流边所进行的操作，是否会对算法正确性有所影响。

对于回流操作正确性的证明

​ 我们知道，残存网络（$residual\ graph$）是一个特殊的流网络，其允许反向边，也即平行边的存在。

​ 那么对于残存网络中，这"特殊"的流 $f'$ ，我们定义 $f \uparrow f’ $ 为流 $f'$ 对 $f$ 的递增操作，定义为：

$$(f\uparrow f')(u,v)=\begin{cases}f(u,v)+f'(u,v)-f'(v,u) &若(u,v)\in E \\0 &其他 \end{cases}$$

​ 在残存网络中将流量发送到反向边上等同于在原来的网络中缩减流量，所以将边 $(u,v)$ 的流量增加 $f'(u,v)$ ，但减少了 $f'(v,u)$ 。在残存网络中，这种将流量推流回去也称为抵消操作（$cancellation$​）。

​

​ 对于上述操作，其满足容量限制性质以及流量守恒性质，证明如下：

​ 先证明容量守恒性质，

​ 设边 $(u,v)\in E$ ，则 $c_f(v,u)=f(u,v)$ ，且 $f'(v,u) \le c_f(v,u)=f(u,v)$ ，因此有，

$$\begin{align*} (f \uparrow f')(u,v) &=f(u,v)+f'(u,v)-f'(v,u)\\ &\ge f(u,v)+f'(u,v)-f(u,v)\\ &=f'(u,v)\\ &\ge 0\\ \\ (f \uparrow f')(u,v) &=f(u,v)+f'(u,v)-f'(v,u)\\ &\le f(u,v)+c_f(u,v)\\ &=f(u,v)+c(u,v)-f(u,v)\\ &=c(u,v) \end{align*}$$

​ 所以，$0 \le (f \uparrow f')(u,v) \le c(u,v)$ ，即该操作满足容量限制性质。

​ 再证明流量守恒性质，

​ 因为 $f$ 和 $f'$ 都遵循流量守恒性质，所以对于所有的节点 $u \in V-\{s,t\}$ ，有，

$$\begin{align*} \sum_{v \in V}(f \uparrow f')(u,v) &=\sum_{v \in V}(f(u,v)+f'(u,v)-f'(v,u))\\ &=\sum_{v \in V}f(u,v)+\sum_{v \in V}f'(u,v)-\sum_{v \in V}f'(v,u)\\ &=\sum_{v \in V}f(v,u)+\sum_{v \in V}f'(v,u)-\sum_{v \in V}f'(u,v)\\ &=\sum_{v \in V}(f(v,u)+f'(v,u)-f'(u,v))\\ &=\sum_{v \in V}(f \uparrow f')(v,u)\\ \end{align*}$$

​ 其中第二行推导到第三行使用了 $f$ 和 $f'$ 的流量守恒性质。

​ 所以，$\sum_{v \in V}(f \uparrow f')(u,v)=\sum_{v \in V}(f \uparrow f')(v,u)$​ ，即该操作满足流量守恒性质。

​ 因此，对于 $f\uparrow f'$​ 这个操作，其满足容量限制性质以及流量守恒性质。

​ 所以回流操作并不会影响到流的基本性质，所以这个操作是正确的。

对于函数 $|f \uparrow f'|$ 值大小的证明

​ 那么如果根据流的值的定义，不妨猜想 $|f \uparrow f'|=|f|+|f'|$​ ，证明如下：

​ 根据定义，有：

$$|f \uparrow f'|=\sum_{v\in V}(f \uparrow f')(s,v)-\sum_{v \in V}(f \uparrow f')(v,s)$$

​ 因为对于每个节点 $v \in V$ ，可以有边 $(s,v)$ 或 $(v,s)$ ，但是二者不允许同时存在。

​ 因此我们定义 $V_1=\{v:(s,v) \in E\}$ 为有边从源节点到达的节点集合，$V_2=\{v:(v,s) \in E\}$ 为有边通往源节点的节点集合。我们有 $V_1 \cup V_2 \subseteq V$ 且 $V_1 \cap V_2 = \emptyset$ 。

​ 所以上式可化为：

$$\begin{align*} |f \uparrow f'| &=\sum_{v\in V}(f \uparrow f')(s,v)-\sum_{v \in V}(f \uparrow f')(v,s)\\ &=\sum_{v\in V_1}(f \uparrow f')(s,v)-\sum_{v \in V_2}(f \uparrow f')(v,s)\\ &=\sum_{v\in V_1}(f(s,v)+f'(s,v)-f'(v,s))-\sum_{v\in V_2}(f(v,s)+f'(v,s)-f'(s,v))\\ &=\sum_{v\in V_1}f(s,v)+\sum_{v\in V_1}f'(s,v)-\sum_{v\in V_1}f'(v,s)-\sum_{v\in V_2}f(v,s)-\sum_{v\in V_2}f'(v,s)+\sum_{v\in V_2}f'(s,v)\\ &=\sum_{v\in V_1}f(s,v)-\sum_{v\in V_2}f(v,s)+\sum_{v \in V_1 \cup V_2}f'(s,v)-\sum_{v \in V_1 \cup V_2}f'(v,s)\\ \end{align*}$$

​ 又因为当 $v \in V_1$ 时，对于在集合 $V_2$ 的边，$v$ 对应的流 $f$ 为 $0$ ，即每一个额外的项都为 $0$ ，反之亦然。

​ 所以可以将 $V_1,V_2,V_1\cup V_2$ 扩展到整个节点范围 $V$ 中。

​ 因此：

$$\begin{align*} |f \uparrow f'| &=\sum_{v\in V_1}f(s,v)-\sum_{v\in V_2}f(v,s)+\sum_{v \in V_1 \cup V_2}f'(s,v)-\sum_{v \in V_1 \cup V_2}f'(v,s)\\ &=\sum_{v\in V}f(s,v)-\sum_{v\in V}f(v,s)+\sum_{v \in V}f'(s,v)-\sum_{v \in V}f'(v,s)\\ &=|f|+|f'|\\ \end{align*}$$

​ 即：$|f \uparrow f'|=|f|+|f'|$

对于合并操作正确性的证明

​ 我们设 $G=(V,E)$ 为一个流网络，设 $f$ 为 $G$ 中的一个流，设 $p$ 为残存网络 $G_f$ 中的一条增广路径。假定将 $f$ 增加 $f_p$ 的量，则函数 $f \uparrow f_p$ 是图 $G$ 中的一个流，由上述证明可知其值为 $|f \uparrow f_p|=|f|+|f_p|$ 。

​ 又因为合并的操作视为 $|f_{p_1} \uparrow f_{p_2}|$ ，所以合并后的值为 $|f_{p_1} \uparrow f_{p_2}|=|f_{p_1}|+|f_{p_2}|$ ，即合并操作是合理的。

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

​ 上述证明解释了为什么我们可以进行回流、合并（$Merge$） 这些操作。那么接下来，我们来证明为什么最后得到的流一定是最大流。该证明也是对最大流最小切割定理的证明。

前置证明准备

​ 我们首先证明对于网络中的一个流以及任意切割 $(\mathcal{S},\mathcal{T})$ ，其净流量 $f(\mathcal{S},\mathcal{T})=|f|$ ：

​ 对于任意节点 $u \in V-\{s,t\}$ ，其流量守恒定律可改写成：

$$\sum_{v \in V}f(v,u)-\sum_{v \in V} f(u,v)=0 \quad\quad①$$

​ 根据 $|f|$ 的定义：$|f|=\sum_{v\in V}f(s,v)-\sum_{v \in V}f(v,s)$ ，我们得到：

$$|f|=\sum_{v\in V}f(s,v)-\sum_{v \in V}f(v,s) \quad\quad②$$

​ 将 $①$ 式针对所有节点 $\mathcal{S}-\{s\}$ 求和并加到 $②$ 中，得到：

$$\begin{align*} |f| &=\sum_{v\in V}f(s,v)-\sum_{v \in V}f(v,s)+\sum_{v \in \mathcal{S}-\{s\}}(\sum_{v\in V}f(u,v)-\sum_{v \in V}f(v,u))\\ &=\sum_{v\in V}f(s,v)-\sum_{v \in V}f(v,s)+\sum_{v \in \mathcal{S}-\{s\}}\sum_{v\in V}f(u,v)-\sum_{v \in \mathcal{S}-\{s\}}\sum_{v \in V}f(v,u)\\ &=\sum_{v\in V}(f(s,v)+\sum_{v \in \mathcal{S}-\{s\}}f(u,v))-\sum_{v \in V}(f(v,s)+\sum_{v \in \mathcal{S}-\{s\}}f(v,u))\\ &=\sum_{v\in V}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in V}\sum_{u \in \mathcal{S}}f(v,u) \end{align*}$$

​ 又因为 $V=\mathcal{S}\cup\mathcal{T}$ 并且 $\mathcal{S} \cap \mathcal{T}=\emptyset$ ，所以可以将上式的 $V$ 进行分解，即：

$$\begin{align*} |f| &=\sum_{v\in V}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in V}\sum_{u \in \mathcal{S}}f(v,u)\\ &=\sum_{v\in \mathcal{S}}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in \mathcal{S}}\sum_{u \in \mathcal{S}}f(v,u)+\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(v,u)\\ &=\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(v,u)+(\sum_{v\in \mathcal{S}}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in \mathcal{S}}\sum_{u \in \mathcal{S}}f(v,u))\\ \end{align*}$$

​ 不难看出，上式括号内的两个求和项是一样的，所以有：

$$|f|=\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(v,u)=f(\mathcal{S},\mathcal{T})$$

​ 综上，净流量 $f(\mathcal{S},\mathcal{T})=|f|$​ 。

​ 由这个性质，我们可以得到一个引理：$|f| \le c(\mathcal{S},\mathcal{T})$ ，证明如下：

$$\begin{align*} |f| &=f(\mathcal{S},\mathcal{T})=\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(v,u)\\ &\le \sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(u,v) \le \sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}c(u,v) = c(\mathcal{S},\mathcal{T}) \end{align*}$$

​ 这个引理给出的一个直接结论就是：一个流网络中最大流的值不能超过该网络最小切割的容量。

最大流最小切割定理

​ 那么接下来，我们就来证明最大流最小切割原理。该原理表明一个最大流的值等于一个最小切割的容量。

​ 最大流最小切割定理：

​ $(1)$ $f$ 是 $G$ 的一个最大流

​ $(2)$ 残存网络 $G_f$ 不包括任何增广路径

​ $(3)$ $|f|=c(\mathcal{S},\mathcal{T})$ ，其中 $(\mathcal{S},\mathcal{T})$ 是流网络 $G$ 的某个切割。即 $|f|_{max}=c_{min}(\mathcal{S},\mathcal{T})$

​ 上述的三个条件是等效的，即三个条件互为充要条件。

​ 以下是最大流最小切割定理的证明：

​ 证 $(1) \to (2)$ ：

​ 假设 $f$ 是 $G$ 的一个最大流，但残存网络 $G_f$ 同时存在一条增广路径 $p$ 。如果我们对 $f$ 增加流量 $f_p$ ，那么 $|f \uparrow f_p|=|f|+|f_p| > |f|$ ，与 $f$ 是最大流矛盾。

​ 证 $(2) \to (3)$ ：

​ 对于节点 $u \in \mathcal{S}$ 和 $v \in \mathcal{T}$ ，如果边 $(u,v) \in E$ ，则必有 $f(u,v)=c(u,v)$ ，否则 $(u,v) \in E_f$ ，上述操作会将 $v$ 置于集合 $\mathcal{S}$ 中。如果边 $(v,u) \in E$ ，则必有 $f(v,u)=0$ ，否则 $c_f(u,v)=f(v,u)$ 将为正值，边 $(u,v)$ 将属于 $E_f$ ，上述操作会将节点 $v$ 置于集合 $\mathcal{S}$ 中。当边 $(u,v)$ 和 $(v,u)$ 都不在 $E$ 中，则 $f(u,v)=f(v,u)=0$ 。因此：

$$f(\mathcal{S},\mathcal{T})=\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(u,v)-\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}f(v,u)=\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}c(u,v)-\sum_{v\in \mathcal{T}}\sum_{u \in \mathcal{S}}0=c(\mathcal{S},\mathcal{T})$$

​ 证 $(3) \to (1)$ ：

​ 由 $|f| \le c(\mathcal{S},\mathcal{T})$ 即可说明 $f$​ 是一个最大流,。

​ 综上所述，$Ford-Fulkerson$ 算法是正确的。

$Edmonds-Karp$​ 算法

​ 简单来说，$Edmonds-Karp$ 算法是 $Ford-Fulkerson$ 算法的一种特殊情况，全部流程跟 $Ford-Fulkerson$ 算法基本一致。

​ 唯一的区别是 $Edmonds-Karp$ 算法在寻找增广路径中，使用寻找无权图最短路径的算法，在残存网络中将所有边的权值视为 $1$​ ，由此来寻找从源节点到汇点的最短路径。

算法实现步骤

参照 $Ford-Fulkerson$ 算法的步骤，对于 $Edmonds-Karp$ 算法的实现步骤只需修改一句话：

• 创建一个残存图 $(residual\ graph)$ ，初始化残存容量
• $while$ 可以找到增广路径 :
  • ==找到最短的增广路径==
  • 找出增广路径中的瓶颈容量 $x$
  • 更新这条增广路径上每一条边，$c_f=c_f-x$​​ ，并删除饱和边
  • 添加该增广路径的回流边

时间复杂度分析

对于寻找最短的增广路径，我们可以使用类 $BFS$ 的算法。

因此寻找最短路径的时间复杂度为：$O(V+E)=O(E)$​

然后循环最多实现 $O(VE)$ 次~~（这里就不证明了吧 详细证明看算法导论）~~

因此时间复杂度为：$O(VE^2)$

*$Dinic$ 算法

​ 下面我们来介绍一个时间复杂度更低，达到了 $O(V^2E)$ 的算法—— $Dinic$ 算法。

$Level\ Graph$ ​

​ $Dinic$ 算法需要用到一个新东西：$Level\ Graph$ 。$Level\ Graph$ 基于 $BFS$ 实现，是一个有权无向图。其随着层数记录每一层的节点，最终到达汇点 $t$ 。

• e.g.

算法实现步骤

该算法的实现与 $Ford-Fulkerson$ 算法类似，但在操作中，我们主要以 $Level\ Graph$ 为主要操作对象：

• 创建一个残存图 $(residual\ graph)$​ ，初始化残存容量
• $while$ 可以找到阻塞流：
  • 用残存图创建 $level\ graph$
  • 在 $level\ graph$ 中找到阻塞流
  • 更新残存图，并添加反向边

图示

• 初始化

• 第一次循环

  • 根据残存图创建 $level\ graph$
  
  • 找到阻塞流，更新残存图
  

• 第二次循环

  • 根据上一次的结果，创建新的 $level\ graph$
  
  • 在 $level\ graph$​ 中找到阻塞流，更新残存图
  

• 第三轮循环

  • 根据上一次的结果，创建新的 $level\ graph$
  
  • 因为没有边能到汇点 $t$ ，循环终止，最终结果如下：
  

时间复杂度

时间复杂度为：$O(V^2E)$

• 若图为一个链表时，有 $n$ 层，循环最多为 $O(V-1)$ 轮
• 每一轮的时间为 $O(VE)$

二部图问题

嘛~有时间在做吧awa 反正是最大流之后的一章(4th edition)

参考文献

1. Wang, Shusen. (n.d.). AdvancedAlgorithms. GitHub. Retrieved April 5, 2022, from https://github.com/wangshusen/AdvancedAlgorithms
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). 算法导论 (第三版). 机械工业出版社.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.). MIT Press.