网络流学习笔记

· · 算法·理论

网络流学习笔记

前言

怕忘了所以写一下，只记录了最基本的算法，未总结问题模型。

什么是网络流

首先说一下什么是网络流。一张有向图，每条边有边权，代表它的容量。每条边还有流量，流量不能超过对应边的容量，且除了源汇点外，每个点的入边流量之和等于出边流量之和。源点为起点，向外输送流量；汇点为终点，收回由源点发出的所有流量。

可以形象地理解为，网络流就是一张水系图。源点为最高点，也是水的源头。汇点为最低点，也是水的尽头。每条河道连接两个地区，并在每个时刻流过固定量的水，这就是流量。每个河道大小不同，因此每个时刻流过的水量限制也不同，这就是容量。除了源点和汇点外，每个地区都是在每个时刻流进多少水就流出多少，水不作停留。

最大流

什么是最大流

由于每个河道有容量限制，因此每个时刻从源点流出的量也有限制。为每个河道规划合理的流量，使从源点流出最大的流量，就是最大流。

朴素算法

怎样求出最大流？首先考虑一个简单的算法，如果我们在一条河道上增加水，那么这些水一定会继续朝下一个地区流，最终形成一条路径。我们定义残量网络来表示原网络每条边还能增加多少水。若原网络中一条边容量为 w，流量为 c，那么残量网络中对应边的边权应为 w-c。

这样，我们在网络中添加水的过程可以看作，在残量网络找到一条从源点 s 到汇点 t 的路径（不含 0 边权），然后设定一个流量 x，再将这条路径上每条边权减去 x。根据贪心，我们尽量使设定的 x 大且合法，因此 x 应取这条路径上边的边权最小值。

重复执行以上算法，直到找不到非 0 路径为止。我们称找到的这些流为阻塞流。容易发现阻塞流不能再添加水了。最大流一定为阻塞流。

Ford–Fulkerson 算法

但是阻塞流不一定为最大流。可以举个简单的例子，先人工找到最大流，然后执行上述算法，就能发现这个简单算法不一定能找到最大流，因为算法中找路径这一过程是随便乱找的，可能找到错误的路径而错过最优解。

解决方法也很简单，我们为每条边再建一条反边，边权为当前流量。这样每条河道 (u,v) 对应两条边，第一条为正向，边权为残量，表示从 u 还能再运输多少给 v；第二条为反向，边权为流量，表示从 v 能还多少水给 u，也就是减少 u 到 v 的实际流量。

选择一条路径时，我们不仅要对路径上的边进行减 x，还要对路径上边对应的反边进行加 x。原因很简单，多给了能还的也多了，多还了能给的也多了。这样我们就不怕选错路径了，因为即使选错，我们还有机会反悔，可以不断调整流量。

执行一次以上路径修改的过程，我们成为寻找增广路。每次找增广路一定会使当前最大流增加，每次找路径的时间复杂度为 O(m)，因此总时间复杂度为 O(fm)。其中 f 为实际最大流大小。这就是 Ford–Fulkerson 算法，也是接下来算法的基础。

Edmonds–Karp 算法

这个算法过程与刚才的算法类似，只是每次找路径为从 s 到 t 的最短路（视所有边权都为 1，注意忽略原为 0 的边权，不然增广无意义）。这样时间复杂度优化到了 O(nm^2)。证明不会，可查看 oi-wiki。

Dinic 算法

仍然是优化以上算法。算法每轮可能会遍历整个残量网络，但只找出一条增广路，就很浪费。所以我们在一次 bfs 后将点按照最短路长度分成若干层，并只保留相邻层之间的连边（类似于最短路图），这样我们随便走都是最短路了。

有了这张分层图之后，我们尝试不断找多条增广路。考虑 dfs 不重不漏地寻找，并同时更新边权。在 dfs 的过程中，每条边仍可能被遍历特别多次，这又是爆炸的时间复杂度。如果遍历完这条边以下的层之后，上面的层的路径边权最小值仍大于 0，这说明这条边已经没有被再更新的必要了，下层路径边权最小值一定等于 0。因为上层最小值大于 0，如果下层也大于 0，那么一定可以继续增广，这就不是阻塞流了。

有了以上思想后，我们为每个点再定义一个 now 数组，表示枚举边的起点。当确定某一条边或某个点没有再枚举的必要时，就将 now 向后移动，避免无用枚举。这就是当前弧优化，也是优于以上算法的关键之处。时间复杂度来到了 O(n^2m)，多加些剪枝能快的飞起。证明略。

最小割

什么是割

割是一种点的划分方式，将所有点划分在两个集合 S 和 T 中，其中源点 s 属于 S，汇点 t 属于 T。割的容量是所有从 S 连向 T 的边的容量和。割的容量最小的割被称为最小割。

最大流最小割定理

引理：任意流小于等于任意割。且取等当且仅当从 S 连向 T 的边都满流，从 T 连向 S 的边均空流。

最大流最小割定理：最大流等于最小割。

证明略。

寻找最小割

根据以上定理，我们先找到最大流。然后从 s 开始，根据刚才的引理，始终走非满流的边，就能找到集合 S，其余的点就是集合 T。

割边数量

如果需要在最小割的前提下最小化割边数量，那么先求出最小割，把没有满流的边容量改成 \infty，满流的边容量改成 1 重新跑一遍最小割就可求出最小割边数量；如果没有最小割的前提，直接把所有边的容量设成 1 ，求一遍最小割就好了。

费用流

什么是费用流

在普通网络的基础上，为每条边 (u,v) 增加单位水费用 c(u,v)，这条河道的费用就是流量乘单价。满足最大流且费用之和最小的流被称作最小费用最大流；满足最大流且费用之和最大的流被称作最大费用最大流。

SSP 算法

与最大流算法一样，基本思想仍是找增广路进行增广。区别在于，基于贪心思想，我们将路径改为以费用为边权的最短路，也就是将 EK 或 Dinic 算法中的 bfs 改为 spfa。因为反边的边权也要取反，所以存在负边权。用 Dinic 实现时注意 dfs 的过程中可能存在 0 环而导致死循环，不满足分层图机构，所以仍需要 vis 数组在递归过程中记录。

注意：SSP 算法不能解决单位费用为负的情况，因为可能会存在负环。

上下界网络流

什么是上下界网络流

顾名思义，就是对于每个河道，其流量既有上限也有下限，即流量必须在区间 [l_i,r_i] 内。

无源汇上下界可行流

给定边的流量上下界，判断是否存在流，使得所有点均平衡。

考虑转化问我们已知的问题，先将流量限制从 [l_i,r_i] 转为 [0,r_i-l_i]，这样就变成了普通网络流。但是转回来的时候需加上 l_i，这导致可能计算好的平衡点变地不平衡了。

尝试用外力使他重新平衡，定义 d_u 为加上后的平衡值。d_u=\sum l_{in}-\sum l_{out}。然后新建立两个点 s 和 t，作为两个外力来源，作用等同于源点和汇点。

如果 d_u<0，那么从 u 连向 t 一条容量为 -d_u 的边，因为加上 l 后出水过多，需将多的出水算入网络流中，模拟会多的出水；如果 d_u>0，那么从 s 连向 u 一条容量为 d_u 的边，因为加上后入水过多，需要将多的入水算入网络流中，模拟会多的入水（这里容易搞反）。此时只有补充边流满时，才可行。而补充边又是以 s 和 t 为源汇点的流，要流满就得最大，所以跑有源汇最大流即可。若最大流能留满所有补充边，说明存在可行解。这样巧妙地解决了不平衡问题。

有源汇上下界可行流

仍然考虑转化为我们学过的问题，考虑消掉源汇点，连一条由 t 到 s，容量为 \infty 的边，这样原本不平衡的两个点通过这条边变平衡了，问题变成了无源汇上下界可行流，使用刚才的方法即可。

有源汇上下界最大流

与找可行流一样，我们先连一条由 t 到 s，容量为 \infty 的边，跑无源汇上下界可行流找到一条可行流。然后再在残量网络上跑普通最大流，两部分拼接起来就是实际最大流。也就是说先找到一条可行流，使所有点平衡，然后加上剩余部分的最大流即可。

有源汇上下界最小流

与上一个极其类似，我们跑完可行流后，同样在残量网络中跑一遍 t 到 s 的最大流（其实就是原网络 s 到 t 的最大流），然后用可行流部分减去最大流部分就能得到最小流啦！