大家好，我是讯享网，很高兴认识大家。

前言

本博客包括较多网络流算法，但其中可能有些错误，可以在评论区指正。

还有些未完善，因为我没太多时间写。

我们在此使用 $E$ 来表示一个图的边集，$V$ 来表示一个图的点集，$F$ 来表示一个图的最大流流量，定义符号 $|S|$ 表示集合 $S$ 的大小，$(u,v)$ 表示从 $u$ 直接连向 $v$ 的一条单向边。

概念

流：一个抽象概念，流可以从一个点出发，通过单向边（即弧）前往另一个点。
弧：一条有向边，可以单向通过流，可以有一个费用，代表每单位的流通过时消耗的费用。
弧的流量：实际通过这条弧的流量。
弧的容量：指的是一条弧的最大流量，流过弧的流量不可以超过弧的容量。
弧的残留容量：指弧还能容纳的流量，即弧的容量减弧当前流量。
弧的单位费用：指一条弧每单位流通过时消耗的费用。
弧的费用：一条弧的费用指弧的流量乘以弧的单位费用。
饱和弧：流量等于容量的弧，即无法增加流量的弧。
零流弧：流量为 $0$ 的弧。
流网络：一个由弧和点组成的图，其中存在一个点入度为 $0$，称作源点，一个点出度为 $0$，称作汇点。
源点：发出流的一个点，拥有无限的流，一般用 $s$ 表示。源点入度为 $0$，出度大于 $0$。
汇点：接收流的一个点，一般用 $t$ 表示。源点出度为 $0$，入度大于 $0$。
网络流：流网络中所有弧上流量的集合。
费用流：流网络中每条弧都有一个费用的情况下，所有弧的流量与费用的集合。
零流：每条弧的流量都为零的网络流。
可行流：当前流网络能够达成的网络流。
最大流：流网络中流量最大的可行流。
最小费用最大流：流网络中弧的费用和最小的最大流。
残留网络：由弧和点组成的一个图，其中每条弧容量为当前网络流中对应弧的残留容量，每条弧有一个反向弧，其容量为原弧在当前流网络中的的流量。
增广路径：残留网络中，从源点 $s$ 到汇点 $t$ 的一条可以有流量的路径。
链：流网络中由若干弧连接成的路径，不一定要求所有弧同向。
前向弧：一条链上和 $u\to v$ 方向相同的边，是这个链的一条前向弧。
后向弧：一条链上和 $u\to v$ 方向相反的边，是这个链的一条后向弧。
割：在流网络中，如果存在一组弧，使得删除这一组弧后，原图从 $s$ 开始无法走向 $t$，则成这组边为原图的一个割。
最小割：单向图中，权值和最小的割。
可行弧：也称允许弧，当 $(i,j)$ 为一个可行弧时，$(i,j)$ 面向汇点。（在最大流某些算法中会有提到）

性质

• 最小割边权和 = 最大流流量

最大流 - FF算法

算法复杂度

时间复杂度 $O((|E|+|V|)F)$

空间复杂度 $O(|E|+|V|)$

算法思想

一个比较暴力的思想。

即每次寻找一条增广路径，然后流入流量。不断重复这个过程，直到无法找到增广路径。

每次从 $s$ 开始 $dfs$，只往残留容量大于 $0$ 的点走，一旦 $dfs$ 到 $t$，立马从 $s$ 引出这条路径可以接受的最大流量经过路径到 $t$。

但是这样的算法是部分错误的。

如图，每条边的容量皆为 $1$，$1$ 为源点，$4$ 为汇点。

讯享网

若第一次找到了 $1\to 2\to 3\to 4$ 这条增广路径，这时 $(1,2),(2,3),(3,4)$ 三条弧的残留容量为 $0$。
第二次 $dfs$ 就无法找到增广路径了，于是计算出来的最大流流量为 $1$。

但实际上，如果我们走 $1\to 2\to 4$ 和 $1\to 3\to 4$ 这两条增广路径，可以得出正确的最大流流量 $2$。

那这个算法不就出错了吗？或者说，如何改进？

我们可以为每个弧增加反向弧，原弧残留容量每减一，就给反向弧残留容量加一。

这样，相当于给算法反悔的机会。

再模拟一遍，第一次找到了 $1\to 2\to 3\to 4$，$(1,2),(2,3),(3,4)$ 三条弧的残留容量为 $0$。$(4,3),(3,2),(2,1)$ 三条弧的残留容量为 $1$。
第二次就可以找到 $1\to 3\to 2\to 4$，于是计算出来的最大流流量为 $2$。

算法正确性得到了保证。

算法流程

使用 bfs 寻找增广路直到无法找到，每次流入增广路所能容纳最大流量。结束时就是最大流。

算法伪代码

暂无 

讯享网

EK算法

算法复杂度

时间复杂度 $O(|V||E{|}^2)$

算法思想

虽然 $FF$ 算法的正确性有保证，但是如果最大流流量 $F$ 过大，$FF$ 算法的时间复杂度会爆炸。

使得其时间爆炸的还是同一张图：

若 $(2,3),(3,2)$ 两条弧容量为 $1$，其余四弧容量为 。

$FF$ 算法会先找到 $1\to 2\to 3\to 4$ 增广路径，发现这条增广路径只能通过 $1$ 流量的流。
然后 $(1,2),(3,4)$ 的残留容量变成了 。$(2,3)$ 残留容量变成了 $0$，$(3,2)$ 残留容量变成了 $1$。
$FF$ 算法继续寻找增广路径，它找到 $1\to 3\to 2\to 4$，再次发现只能通过 $1$ 流量的流。
然后 $(1,3),(2,4)$ 的残留容量变成了 。$(3,2)$ 残留容量变成了 $0$，$(2,3)$ 残留容量变成了 $1$。

…

如此往复，我们发现 $FF$ 算法寻找了 $2^{32}-1$ 次增广路径，最终计算出了最大流。

这显然毫无疑问 $TLE$ 了。于是 $FF$ 算法的改进版 $EK$ 算法应运而生。

$EK$ 算法只是做了一个小改变：它将 $FF$ 算法的 $dfs$ 改成了 $bfs$，这样便不会绕远路了。

每次寻找最短路，第一次寻找到的就是 $1\to 2\to 4$。

算法流程

$EK$ 算法使用 $bfs$ 寻找增广路径，对于每条找到的增广路径，使用和 $FF$ 算法一样的方法，从源点 $s$ 顺着增广路径流入最大流量的流。

算法伪代码

讯享网暂无 

Dinic 算法

算法复杂度

时间复杂度 $O(|V{|}^2|E|)$

空间复杂度 $O(|V|+|E|)$

算法思想

$EK$ 算法问世之后，$Dinitz$ 大佬觉得还不够快，于是再次改进得到了 $Dinic$ 算法。

$Dinic$ 算法使用和 $FF$ 算法相同的 $dfs$ 寻找增广路径，但是在每次寻找增广路径前， $Dinic$ 先跑一遍 $bfs$，用于标记到源点 $s$ 的最短距离。

在 $dfs$ 过程中，每个点只尝试往更远的点推进流，于是速度又再次提升。

算法流程

先使用 $bfs$ 来标记每个点到 $s$ 的最短距离。

然后 $dfs$，$dfs$ 过程中每个点只尝试往离源点距离更远的点遍历。最终如果能 $dfs$ 到 汇点 $t$，则代表存在增广路径，流入流。

接下来，重新 $bfs$ 标记距离，反复执行以上操作，直到无增广路径。

算法伪代码

暂无 

算法优化

$Dinic$ 算法又有几个优化可以学习：

当前弧优化：开一个数组记录每个节点访问到第几条弧，下次经过节点时就可跳过满流的弧，访问下一个弧，不需要再判断前面的弧是否满流。

多路增广：在某点 $dfs$ 找到增广路后，如果还剩下多余的流量未用，可以继续在该点 $dfs$ 尝试找到更多增广路。

爆点：寻找增广路线过程中，如果当前节点的所有出弧都满流了，那么这个节点就不再使用了。具体操作就是，存储层数的数据把这个节点的层数标记为负数。

预流推进算法

算法复杂度

时间复杂度 $O()$

空间复杂度 $O(|V|+|E|)$

算法思想

预流推进算法中，每个节点可以储存流，而存有流的节点称为活动节点。

而源点 $s$ 一直都是活动节点，汇点 $t$ 一直不是活动节点。

预流推进算法通过一直对活动节点推流，最终求出最大流。

算法流程

预流推进算法每次选择一个活动节点，尝试对其进行推流，即将这个节点储存的流推向其他节点。

当没有活动节点（除源点）时，算法结束，汇点的流就是最大流。

但是以上算法也有部分问题，若两个点之间来回推流，容易导致超时。

我们可以给每个点高度，规定流只能从高往低处流，平地也可以流。

每次推流时将被推流的点高度增加。

这样当两个点不停推流时，会有一刻高度超过旁边的点，于是流会被推到另一个点。

算法伪代码

讯享网暂无 

HLPP算法

算法复杂度

时间复杂度： $O(|V{|}^2\sqrt{|E|})$

空间复杂度： $O(|V|+|E|)$

算法思想

HLPP 算法，也称最高标号预留推进算法。

预留推进我们会了，但最高标号是什么？

在预留推进算法前进行一次汇点 $t$ 开始的 $bfs$，计算每个点到 $t$ 的最短路长度 $dis$，我们每次推流选择离 $t$ 最远的，并且只往低处推。

若出现一个活动节点所有的边都满流了，则将这个活动节点抬升高度，这样就可以让多余的流被推回去。

算法流程

从汇点开始 $bfs$，计算出每个点到 $t$ 的最短距离 $dis$。（和 $dinic$ 相似）
首先将与 $s$ 相连的边设为满流，并将这时产生的活动结点加入优先队列 $Q$。（$Q$ 中以 $dis$ 排序）
重复以下过程直到 $Q$ 为空：

1. 选出 $Q$ 最上方的活动结点 $u$，并依次判断残留网络中每条边 $(u,v)$，若 $di{s}_u=di{s}_v+1$，则顺着这些边推流，直到 $Q$ 变成非活动结点。
2. 若 $u$ 在往所有相邻的点 $v$ 推流后还是活动结点。则需要对 $u$ 进行重新标号：$di{s}_u=\underset{(u,v)\in G^{\prime }}{\min }(di{s}_v+1)$。（$G^{\prime }$ 为残留网络）然后再将 $u$ 加入队列。

SAP算法

$SAP$，全称 $ShortestAugmentPath$，最短增广路径算法。

由于网上资料太少，而且真实性存疑，所以。。。这算法不学也罢（

算法复杂度

？？

算法思想

？？

算法流程

？？

算法伪代码

？？ 

ISAP算法

算法复杂度

时间复杂度 $O(|V{|}^2|E|)$

空间复杂度 $O(|V|+|E|)$

算法思想

$ISAP$ 算法，全称 $ImprovedShortestAugmentPath$，即改进的最短增广路径算法。

$ISAP$ 算法是 $Dinic$ 算法的另一种优化版本，$Dinic$ 算法每次跑 $dfs$ 前需要一次 $bfs$ 来标记序号，而 $ISAP$ 算法通过直接修改标号，不 $bfs$ 来降低时间复杂度。

算法流程：

与 $Dinic$ 算法不太相同的是，$d_u$ 代表到汇点 $t$ 的最短距离。

$ISAP$ 算法在开始前需要初始化出每个点的最短距离 $d_u$。

1. 使用 $dfs$ 寻找一个增广路径，使得路径上的点的 $d$ 值单调递减且相邻的差为 $1$。
2. 往增广路径中流入流。
3. 枚举增广路径上所有点，若有点 $u$ 满足 $(\forall v\in G,(u,v)\in E)(d_v\ne d_u+1)$（其中，$G^{\prime }$ 为残留网络），则需要更改这个节点的最短距离， d u = min ⁡ ( u , v ) ∈ G ′ { d v + 1 } d_u = \min\limits_{(u,v)\in G'}\{d_v + 1\} du​=(u,v)∈G′min​{ dv​+1}。特殊地，若残留网络上 $u$ 无出边，则 $d_u=n$。

当不存在增广路径时，算法结束。或者说，当 $d_s>=n$ 时，算法结束。

算法优化

当前弧优化：在 $Dinic$ 算法中讲过了，这里不讲了。

GAP优化：因为寻找的增广路径上的节点 $d$ 值序列必然是 { 1 , 2 , 3 , 4 , 5 , . . . } \{1,2,3,4,5,...\} { 1,2,3,4,5,...}，所以当某一个距离标号不存在时（称之为断层），就没有最短路径了，我们可以提前将算法结束。

MPM 算法

算法时间复杂度

费用流算法

SSP算法

该算法每次尝试寻找源点 $s$ 到汇点 $t$ 单位费用最小的增广路径，并流入可行的最大流。

所以只需要将 $EK$ 算法的 $bfs$ 更改为寻找最短路的 $SPFA$ 即可。

此算法在计算有负环的流网络时会出现错误，需要运用消圈算法来消去负环。

ZKW算法

网络流应用及各类题型