网络流,分为最大流与费用流。

最大流,其实就是运输流量最大化,给定起点$s$,终点$t$,再给你一边集,每一条边都有不同的流量让你求出$s->t$的最大流量。

网络流必须遵守三大法则:

  1. 容量限制,即一条边实际通过的流量$f(x,y)$不能超过边的容量$c(x,y)$大小。
  2. 斜对称,$f(x,y)=-f(y,x)$,对于程序最大化流量有很大的帮助。
  3. 流量守恒,也就是$\sum_{x,y\ne s,t} f(x,y)=0 $

有剩余容量$cf(x,y)=c(x,y)-f(x,y)$,便有剩余网络,用于显示网络中可用容量有多少。

对于反向弧而言,初始剩余容量为$0$,如果正向弧通过了$x$单位的流量,反向弧就相应的增加$x$单位的剩余容量,这个操作意味着未来流量可以通过反向弧跑回去,对最大流量进行贡献

因为单次$s->t$的路径的流量可能不是最大流量,因此剩余网络中,正向弧(给定的边)与反向弧(给定的边的反边)会交织成一条增广路,使得流量可以继续通过,这个可以称之为反悔

EK

根据这个思路,可以衍生出EK龟速网络流,每次仅对单条增广路进行操作,龟得不行。

EK龟速网络流可以衍生稍微高级一点的Dicnic

Dicnic

先介绍一下分层图吧,为了防止流量在两个点流来流去不走了,因此需要bfs遍历一下访问点的顺序,同时判断是否能到达终点。

Dicnic同时对多条增广路径进行操作,分为dfs版本和bfs版本,dfs版本相对好写一点。

对于当前点$x$,所携带的流量$f$,对于剩余网络中的$(x,y)$,如果$x$已经运出去的流量$s$小于$f$,

则可以往$y$运送$\min\{cf(x,y),f\}$的流量,如果还有剩余,还可以运到另外的$y$。

优化

当前弧优化:考虑当前分层图$x$,对于邻接表而言,每一次访问,开头总会有一段没有流量的弧,而这一段恰好就是要优化的,记得更新分层图时重置优化。

奇怪减枝,按照分层图走。

代码

ISAP

ISAP这的挺好学的,有了dicnic的思路之后,理解起来不难。

与dicnic相似的,ISAP一样要建分层图,但是ISAP只用建一次。

如何维护分层图呢?

有$d_x$表示$x$距离$t$的距离。

如果$x$没有了出度,即当前分层图中,流量到了$x$就进入了死胡同,出不去了。

为了让$x$的流量能出去,必然要改变$d_x$,增加$x$到$t$的距离。

增加多少取决于有现有流量的边$(x,y_i)$中,最小的$d_{y_i}+1$即为$d_x$

在代码实现中,可以以$d_x+1$的方式累加到$d_{y_i}+1$,并不影响答案。

优化

加上各种优化,比如弧优化,Gap优化等等,常数小的一匹,完爆dicnic。

关于Gap优化,实际上就是断层没断层,如果断层了,就没有增广路了。

Gap正确性证明

代码

最高标号预流推进HLPP

虽然时间复杂度上看起来更优$O(n^2\sqrt{m})$,但是在随机图下,却没有ISAP快。

HLPP采用的也是分层图结构,不过它是实时流动,也就是实时更新分层图。

初始只有$s$的层次为$n$,其它待搜索,均为$0$。

与ISAP相似的,如果一个点所携带的流量推不出去了,就改变它在分层图的层次,具体也就是在残存流量图中,与它相邻的点取最小的一个$+1$,就是它的层次。

同样可以使用Gap优化,来减少状态。

代码


把所有的最大流模板打完之后,可以考虑一些理论知识了。

定义:定理两个集合$S,T$,网络中一部分的点归于$S$,其余的点归于$T$,把所有的从$S$到T的正向弧割掉,所有被割的正向弧的容量之和即为一个割。

求证:最小割等于最大流

简要证明:

对于一个不是最大流的流来讲,一定存在从$s$到$t$的增广路,剩余网络构不成割。

这个仔细讲一讲吧,因为一个割,割掉了所有从$s$通往$t$的路径,而容量$c(x,y)$始终大于等于流量$f(x,y)$。

因此这些割边的容量之和,定然大于等于最大流,如果再不懂就往下看吧。

从这个可以得出:任意流,都小于等于任意割;也可以得知最大流是最小割。

具体证明:

若剩余网络中不存在增广路,把整个点集看作$V$,$s$通过剩余网络可以达到的点集为$S$,$T=V-S$。

考虑$\forall x\in S,y\in T,(x,y)$存在,$cf(x,y)$必然为$0$,即边流量达到容量上限,否则会有增广路。

从另一个方面出发,这些边就可以构成一个割集。

因此最大流等于最小割。