网络流

前言

首先，网络流不是一个算法，而是一个整合包（玩MC玩的），说白了就是网络流是多个算法的统称：

• 最大流
  • EK
  • Dinic
• 最小割
• 费用流
• …

而且，有些不常用的，可能就不会提，粘个OI Wiki的链接就不详细写了。

接下来就按照这个目录挨个讲一下每个算法。

最大流

如果有哪里没有说清楚，可以看这里，里面还有我没有说到的最大流类型。

看到最大流这个名字很多人都很陌生，这里就先从定义说起。

定义

还是拆词法，“网络流”就可以大致理解为“网络”上的“流”，接下来就挨个说一下这两个的定义。

网络

先说网络的定义。（当然不是Internet）

我们在理解的时候可以认为是管道，但实际上它是一张特殊的有向图。

建设管道的必然知道，管道内流过的水，准确来说是单位时间内流过的水，必然是有上限限制的，否则管道就炸了。

这里也一样，对于每条边 $x \to y$，都有一个函数 $c(x,y)$ 表示这条边的限制，又称容量。

如果在图上没有这条边，则统一规定 $c(x,y)=0$。

最后，还是跟最短路一样，它有一个起点和一个终点，又称源点 $S$ 和汇点 $T$（$S \not= T$）。

流函数

再说流函数。

流函数就是说，在真实操作中，一个单位时间内一条边 $x \to y$ 流过的水量 $f(x,y)$。

这里默认保证每个单位时间内都得流过这么多。

其实很好理解。

流函数性质

顺便说一下流函数要满足的性质。

首先，源点可以无限输出水，汇点可以无限输入水。

接下来就是一堆性质：

• 对于每个 $x,y$，显然 $f(x,y) \leq c(x,y)$（容量限制）。
• 对于每个 $x,y$，$f(x,y)=-f(y,x)$（斜对称）。
• 对于每个 $x$，满足不是源点也不是汇点，$\sum\limits_{u \to x} f(u,x)=\sum\limits_{x \to v} f(x,v)$（流量守恒）。

这里说一下最后一点性质。

首先，$u \to x$ 即代表对于每个 $u$ 满足 $u$ 到 $x$ 有边，$x \to v$ 同理。

其次，这个翻译过来就是说，对于不是源点不是汇点的任何点，它们都不会凭空产生水，也不会让水凭空消失。

而源点和汇点呢？源点就没有入，凭空产生水；汇点就没有出，让水凭空消失。

容易理解

流量

说到流，那必定要提流量。（当然不是你们家的网络流量）

其实流量就是上面说的“流过的水量”，说白了就是 $f(x,y)$。

这里说一下一个细节，$f$ 是流函数，$f(x,y)$ 是该边的流量。

同时，还有一个反面定义，就是 $c(x,y)-f(x,y)$ 为该边的剩余容量。

（注意上面两个加粗题的表达）

但这只是一条边的流量，如果扩展到一张图，根据流量守恒，直接看源点输出了多少水，就是整张图的流量。

也即汇点输入的水量。

最大流

最后再说最大流的定义。

这里说一下，最大流其实是一个函数，就是流函数。

而与它仅差一个字的最大流量，才是一个数值，即最大流对应方案的流量。

（不过似乎没有很多人会在乎这两个定义的差别，底下的所谓“求最大流”的算法，应该是“求最大流量”）

说完这个后，顾名思义就能猜到定义了。

就是合法的流函数有很多，使得整张图的流量最大的流函数，就是最大流。

EK（Edmonds Karp）

说完定义，接下来就从最基础的EK算法说起。

这个算法复杂度很高（至少相对Dinic而言），但它确实是所有网络流算法的基础。

因为Dinic就是从EK上优化的，最小割、费用流都是以Dinic为基础的。

接下来先讲实现，再讲原理。

不过一般没人写EK。

实现

而且，其实EK和二分图（匈牙利算法）很像，都是求增广路。

说白了，就是当前解不优，找一个更优的。

其本质就是反悔贪心。

而此处的增广其实是这么实现的：

• 先建图，带权，同时建一个反向的、边权为 $0$ 的边。
  • 即对于原图中的一条边 $(u \to v, w)$，建两条边：
    • $(u \to v,w)$
    • $(v \to u,0)$
  • 注意一下，不要对这里的反向边有“种族歧视”，就把反向边当做是普通的边，人人平等（
• 然后，不断做这件事：
  • 从源点开始BFS，中途记录一下当前所有经过的边的边权最小值。
  • 如果BFS到了汇点，答案加上最小值 $val$。
  • 同时对于每条经过的边：
    • 让这条边的边权减去 $val$。
    • 让它反向边边权加上 $val$。
• 直到从源点开始，无论如何都得经过一条边权为 $0$ 的边才能到汇点为止。
• 因为如果经过一条边权为 $0$ 的边，此时就不用往下搜了。
• 最后，直接输出答案，即所有最小值之和即可。

接下来说原理。

原理

首先，说一下加反向边的大致意思。

其实就是说，你在反向边上流过 $v$ 的水，就相当于让这条边少流 $v$ 的水。

其次，说一下BFS这部分的原理。

还是举具体的例子。

在这张图里，我们模拟一下，首先一定找的是 $1 \to 2 \to 3 \to 4$ 这条路径。

随后把反向边更新。

（注：在边上面，黑色的是原本边的边权；在边下面，红色的是反向边的边权）

接下来增广的是 $1 \to 5 \to 3 \to 2 \to 6 \to 4$ 这条路径。

此时已经无法继续增广。

所以最终答案为 $2+2=4$。

而怎么理解呢？其实只是这个返回的机制很独特而已。

我先BFS到 $1 \to 5 \to 3$，然后把最开始的路径 $3 \to 4$ 部分拼走了。

此时最开始的路径中的 $1 \to 2$ 开始重新寻路，就把增广路径中的 $2 \to 6 \to 4$ 拼走了。

所以最后是两条路径：

• $1 \to 5 \to 3 \to 4$
• $1 \to 2 \to 6 \to 4$

答案为 $4$。

复杂度

$O(nm^2)$

其中 $n$ 为点数，$m$ 为边数。

证明之后补

网上的证明

Dinic

接下来就是重头戏了，就是Dinic算法。

这个算法相比而言，复杂度就小了很多。

并且，在求二分图最大匹配方面，比匈牙利算法跑得更快。

这次跟上面反过来，先说原理再说实现。

原理

首先，我们考虑一下EK算法为何复杂度如此之大。

其实就是因为，它每次都得进行BFS，每次都从源点开始搜到汇点。

但做了这么多功，不还是只能搜一条增广路吗。

这就导致花的时间很多，但得到的收益很少。

所以我们就对症下药。

也就是我们可以一次搜多条最短路。

不过准确来说，我们是不一定每次都从源点开始，就像遍历一棵树一样，每次都从当前点开始搜。

这样的话复杂度就能剩很多。

实现

原理很好解释清楚，但实现其实细节很多。

这会虽然也用BFS，但实际上上面已经透露了，Dinic的核心在于DFS，所以BFS只求最短路。

具体来说，我们是这样实现的：

• 只要图还连通，就从源点开始做一遍BFS，求出现在源点到每个点 $i$ 的距离 $dis_i$。
  • 此时就不断做DFS，并进行增广，直到不能增广为止。
    • 一次DFS的返回值是多次增广的结果之和。
  • 将答案加上返回值。

说一下，连通的意思是存在一条路径从源点到汇点且不经过边权为 $0$ 的边；同理，边权为 $0$ 的边是不可经过的。

接下来就是重头戏了，就是DFS的具体实现。

首先，上面EK算法里，由于用BFS实现，所以每次增广都是走的当前的最短路。

显然这也是最优的。

那在这里，我们也得保证一定要最短。

咋做呢？我们不是BFS出了距离 $dis_i$ 吗？我们干脆在DFS的时候只遍历最短路图即可。

即对于一个点 $x$，只遍历满足 $dis_{to}=dis_x+1$ 的出点 $to$。

还是跟之前差不多（至少有点雷同的思想），直接放实现：

• DFS传入两个参数，一个是当前点 $x$，一个是流到点 $x$ 的水量 $lim$。
  • 遍历 $x$ 的每个满足条件的出点 $to$，设这条边的边权为 $len$。
    • DFS下去，并且给出点 $to$ 以 $\min(lim,len)$ 的水。
    • 【优化】如果说发现DFS的返回值（设为 $val$）为 $0$，则说明该子树无法增广，直接将该出点标记不可访问。
      • 这一步有一个很好的实现方式，就是把 $dis_{to}$ 设为 $0$，此时一定不会被遍历到。
    • 更新 $x \to to$ 及其反向边的边权。
    • 由于 $val$ 的水已经从 $x$ 流出，所以 $lim$ 减去 $val$。
    • 【优化】如果 $lim$ 为 $0$ 了，则水已经不可能再流出了，直接退出循环。
    • 这里注意一个点，就是虽然给 $to$ 提供了 $\min(lim,len)$ 的水，但其实真正流出去的只有 $val$ 单位的水，所以所有更新都应该用 $val$，完全与 $\min(lim,len)$ 无关。
  • 【优化】这个优化被称为“当前弧优化”：
    • 我们考虑一下，显然一个点可能被DFS多遍。
    • 而每次我们都遍历一遍所有出点吗？显然不是。
    • 那么我们每次就记录一下遍历到哪个出点了。
    • 下次就直接从这个出点开始遍历。
    • 此处就有两种实现方式了：
      1. 使用vector建图，记录当前遍历到的下标。
      2. 使用链式前向星建图，不断更新表头。
    • 但要注意一下，第2种方法在更改表头之后，要记得还原回来，否则会出错。

据说还有MPM算法、ISAP之类的，这里就不说了。

复杂度

$O(n^2m)$

其中 $n$ 为点数，$m$ 为边数。

证明之后补

网上的证明

但这个只是上界，在一般的网络内，是往往达不到的。

比如说，在 $n \leq 10^4,m \leq 10^5$ 的题目内，用Dinic只跑了 $300~\text{ms}$。

二分图

参考：这里

这里顺便说一下如何用Dinic去求二分图最大匹配。

既然是图论算法，难点必然在于建图。

而这里怎么建呢？直接上结论：

• 从源点往每个二分图的左侧点连容量为 $1$ 的边。
• 从每个二分图的右侧点往源点连容量为 $1$ 的边。
• 二分图的左右侧点之间仿照二分图连法连容量为 $1$ 的边。

然后跑最大流即可。

由于图的特殊性，此时复杂度最多为 $O(m\sqrt{n})$，与匈牙利算法的 $O(nm)$ 差了一个根号。

最小割

如果有哪里没有说清楚，可以看这里。

说完最大流，再说一个与它息息相关的最小割。

还是先从定义说起。

定义

对于一个网络（就是一张有向图）$G=(V,E)$ 来说，如果存在一个边集 $E’$ 满足 $E’ \subseteq E$。

且从 $G$ 中删去 $E’$ 的边后，该网络的源点和汇点不再连通。

那么 $E’$ 边集被称为割，其中的任意一条边满足 $e \in E’$ 都被称为割边。

而使得所有割边的容量之和最小的割，被称为是最小割。

求值

接下来说求值。

其实可以八个字搞定：

• 最小割等于最大流

理论上这个不严谨，我们把它严谨化一下：

• 对于任意一个网络，该网络的最大容量，等于该网络的最小割中所有割边的容量之和

所以其实直接求最大流即可。

证明

之后补

网上的

费用流

时隔多年，终于可以补一下费用流的坑了。

定义

首先我们需要先明白费用流是什么。

其实就是在网络流的流量限制之外，还多了一个每流过一单位的流量需要花费的代价。

一般分为两种：

• 最小费用最大流，就是说保证最大流的情况下把费用最小化。
• 最小费用流，就是不用保证最大流，把费用最小化即可。

实现

直接讲实现。

其实费用流的实现比最大流简单多了。

最小费用最大流

直接：

• 不断按单位代价作为边长跑SPFA。
  • 只要SPFA还能走出来（不经过 $len=0$ 的边），就继续。
  • 然后把SPFA最短路路径上所有边流过“边权的最小值”的流量。
  • 更新答案。

所以最后的复杂度就是 $O($ 增广次数 $\times$ SPFA复杂度 $)$。

这个东西一看就很玄学，结果就是这样的。

增广次数可能会被卡到流量级别（特殊构造数据情况下），SPFA则是 $O(nm)$ 最多。

所以说一半费用流如果确定要用，且这样建图一定最优，必然是给放过的。

不过注意一下，有时候一点不同的建图方式就是大相径庭的运行效率。

最小费用流

稍微改一下。

既然我们需要通过不断SPFA来增广。

那么只要SPFA出来的最短路 $>0$，那么最后的费用一定不是最小了。

于是直接：

• 不断按单位代价作为边长跑SPFA。
  • 只要SPFA还能走出来（不经过 $len=0$ 的边），就继续。
  • 如果最短路 $>0$，退出循环。
  • 把SPFA最短路路径上所有边流过“边权的最小值”的流量。
  • 更新答案。

复杂度同上。

网上的讲解