最大流算法

Published: by Creative Commons Licence

  • Tags:

一些网络流问题

无源汇有上下界可行流

题目:给定$n$个点和$m$条边组成的图$G$,每条边都有一个流量上限和下限,求一种流量方案,使得每个顶点流量平衡且每条边的流量都合法。

首先我们让图上跑着一个流$F$,每条边上的流量都是它的下限。这个流如果是不可行的,那么只有一个可能,一些顶点的流量不守恒。我们可以建立另外一张图$G'$,每条边的容量为上限减去下限。由于一些顶点的流量不守恒,我们可以选择释放或追加一些流量来帮助其平衡。做法就是加入一个新的源点和汇点,之后对于每一条边$(u,v)$,我们建立一条从源点到$v$的边,同时建立一条从$u$到汇点的边,容量均为$(u,v)$的下限。

在图$G'$上跑出最大流$F'$后,我们检查每个与源点和汇点相连的边是否被跑满了流,如果不,就无解。因为如果存在可行流,我们将所有边的流量减去下限,这样原图的部分顶点流量就会不守恒,不守恒的部分会借由与源点相连的边或与汇点相连的边流入或流出,这样就能得到跑满的最大流了。

在图$G'$上跑出最大流$F'$后,我们发现$F'+F$是一个可行流,只要删除源点和汇点即可。

LOJ上的模板题

有源汇有上下界最大流

题目:给定$n$个点和$m$条边,其中顶点$1$是源点,顶点$n$是汇点。每条边都有一个流量上限和下限,求一种流量最大的方案,使得每个顶点流量平衡且每条边的流量都合法。

首先我们跑出一个可行流。但是这里与无源汇有上下界可行流优点不同,就是顶点$1$和$n$允许流量不守恒,准确的说$1$允许入流减出流为负数,而$n$允许入流减出流为正数。这里我们可以从$n$到$1$加一条辅助边,边的容量为无穷。这样跑出了可行流后,删除辅助边得到的还是可行流。

接下来我们考虑如何在可行流的基础上找到最大流,如果我们直接在可行流上跑,就会导致一些边的流量低于下限。简单的方式就是我们在图$G'$的残存网络上跑从顶点$1$到顶点$n$的最大流,尽管图上原先加入的源点和汇点会的流量不守恒,但是与它们相连的边的流量是不会改变的,因此可以直接忽略原先的源点和汇点。。

LOJ上的模板题

有源汇有上下界最小流

题目:给定$n$个点和$m$条边,其中顶点$1$是源点,顶点$n$是汇点。每条边都有一个流量上限和下限,求一种流量最小的方案,使得每个顶点流量平衡且每条边的流量都合法。

类似于有源汇有上下界最大流,我们先跑出一个可行流,不同点是最后是从$n$向顶点$1$跑最大流,即我们要回退尽可能的流。

LOJ上的模板题

最小割

从网络流中删除总容量最少的边,使得s所在连通块与t所在连通块不连通,被删除的边集称为最小割。

最小割最大流定理:最小割的总容量与网络中最大流相等。

我们要求$s$与$t$最小割,可以通过最大流算法跑出最大流,之后将与$s$连通的顶点集合记作$S$,将与$t$连通的顶点集合记作$T$,这时候$S\cap T=\emptyset$,而所有从$S$到$T$的边都是被割去的边。

平面图最小割

给定$n\cdot m$矩阵,左上角是起点,右下角是终点。有些网格是不可通行的。且两个相邻的顶点之间存在一条边,边权给定。现在求该图的一个最小割。其中$n,m\leq 1000$。

直接上最小割会TLE,因为图太大了。要解决这个问题,我们需要知道如果将平面图转换成对偶图,转换成对偶图后,原图的每个割都对应对偶图中从起点到终点的一条路径,而最小割则对应最短路。因此问题可以通过dijkstra算法解决,时间复杂度为$O(nm\log_2nm)$。

提供一道BZOJ题目

这里推荐一篇博客,里面讲解了怎么将平面图转换为对偶图,顺便借一张图。

https://img-blog.csdn.net/20170508220154021?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvenh3MDgxOQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast

最多割集划分

给定一个包含$n$个顶点,$m$条边的无向图,给定起点$s$和终点$t$,要求找到最多的不相交边集,使得任意一个边集的删除都会导致$s$和$t$的不连通(即边集是$s$到$t$的一个割集)。

讲一下我的思维轨迹吧,这道题还是比较取巧的。

首先这个题目问的是存在多少割,注意到如果图是平面图,那么我们将其转成对偶图,问题就变成了存在多少从起点到终点的不相交的路径,这个是独占路问题,可以用最大流求解。

到这里一切都很完美,直到我发现图不一定是平面图。

接下来就可以尝试非常直接的想法,从起点跑最短路,之后将图分成$d(t)$层,我们之后可以给出$d(t)$个不相交边集,其中第$i$个边集由距离为$d(i)$与$d(i+1)$的顶点之间的边构成。

可以发现这个想法中,得到的结果一定是不相交的,同时每个集合也都是原图的一个割集。现在只需要证明不存在数量更大的不相交割集。

这个一开始我用的归纳法,发现不好证明。但是紧接着发现一个非常简单的证明方式:任意考虑从$s$到$t$的一条最短路,其长度为$d(t)$。很显然每个割集都至少会包含这条最短路上的至少一个顶点(否则就不是割集了),而这些割集又不相交,因此可以直接推出不相交割集的数目上限为$d(t)$个。

时间复杂度为$O(n+m)$。

提供一道题目

最大权闭合图

对于一个有向图G=(V,E),我们称V的一个子集U为闭合图,如果对于所有边$(u,v)\in E$,有$u\in U\Rightarrow v\in U$。

如果每个顶点都有对应的权值,称总权最大的闭合图为最大权闭合图。

我们可以建立一个对应的图$G'=(V',E')$来计算最大权闭合图。我们通过向V中加入两个新结点s,t得到$V'$,即$V'=V+{s,t}$。而对于E中的每一条边,我们在G'中建立对应的一条边,但是容量设为无穷。对于每一个结点u,如果w(u)的权大于0,我们则建立一条边(s,u),容量为w(u)。而如果w(u)为负数,我们就建立一条边(u,t),容量为-w(u)。如果w(u)为0,那就不用管。

考虑G'中的一个最小割,由于流量最多为所有结点权值之和,因此最小割中的边容量均不可能超过该上界,即原图中的有向边(容量为无穷)不会出现在最小割中。

简单割是指这样的一个割,其中每条边至少有一个端点为s或t。而很显然图G'只有简单割。

最小割将V'划分为两个连通的集合S与T。而$X=S\cap V$一定是一个闭合图,否则就存在这样一条边$(u,v)\in E$,$u\in X$且$v\in V-X$,但是这也说明X与v不连通,即边(u,v)属于最小割,而这与最小割是简单割相悖。

对于任意闭合图X,我们可以选择从G'中删除所有从X到t的边,以及从s到$V-X$中的边,这些边组成的就是最小割,而剩下的$S=X+s$。

我们记$A=S-s$,$B=T-t$,记$A^+$表示A中所有权重大于等于0的结点集合,而$A^-$表示A中所有权重小于0的结点集合,对于B同样。

由于简单割覆盖了所有S到t的边,以及s到T的边,因此简单割应该满足$cut(G')=B^++(-A^-)$,这里表示的集合中所有结点的权值之和。

而图A的权值之和应该为满足下面性质:

这里$A^+$表示的是集合$A^+$的总权值,其它类似。当A的总权值最大时,显然$cut(G')$最小,因此我们只需要计算出图G'的最小割之后代入上面公式即可得到闭图的最大权,而闭图此时为$S-s$。

提供一道Atcoder的题目

独占路问题

问题1:给定一副$n$个顶点$m$条边的无向图。现在希望找到$k$条从顶点$1$到顶点$n$的路径,且所有路径都没有公共边。

我们可以建立一个网络流,每条边的容量均为1,之后找到任意一个流量为$k$的流即可。那么如果从流中提取出$k$条路径呢,非常简单我们直接从顶点$1$开始DFS,直到抵达顶点$n$为止。由于除了源点和汇点外,其余所有顶点都是流量平衡的,即入流等于出流,因此我们一定能找到这样的$k$条路径。每次找到路径后,删除路径中出现的边,总共跑$k$次DFS即可。

时间复杂度为$O(\min(n^2m,km))$。

问题2:给定一副$n$个顶点$m$条边的无向图,每条边都有一个长度。现在希望找到$k$条从顶点$1$到顶点$n$的最短路径(每条路径都是最短路),且所有最短路径都没有公共边。

在问题1的基础上,我们将网络流替换成费用流,每条边的费用为长度,容量为1。假设最短路为$L$,那么我们只要要求流量为$k$的最小费用流费用正好为$kL$即可。首先由于沿最小费用路径增广,每次的增广的费用都是非严格递增的,而第一次增广的费用为$L$,因此增广$k$次的费用至少为$kL$。同时如果存在满足条件的$k$条路径,一定可以搞出这样的流。现在来考虑第二个问题,我们DFS出来的路径一定是最短路,这是必然的,假如我们DFS出长度超过$L$的路径,那么剩下的$k-1$条增广路径的总费用小于$(k-1)L$,这与$k-1$的最小费用流的费用至少为$(k-1)L$相悖。

时间复杂度为$O(knm)$。

最大密度图

假设有图G=(V,E),要求找其中一个子图G'=(V',E'),使得边数与顶点数的比值尽可能大:

符合上述条件的图称为最大密度图。

由于是分数最大化,且分母始终大于0,很容易想到分数规划。分数规划通过不断解决下面过程来二分搜索最终的结果:

要解决上面的问题,我们可以创建一个新图,为G中每个结点和边都在新图中建立一个对应结点,边对应的结点的权值为1,而结点对应的结点的权值为-c。由于选择某条边加入G'的前提是边的两个端点都已经加入了G',因此我们需要在新图中建立对应的依赖关系,从边对应的结点向其端点添加一条单向边。到此,求解$h(c)$的问题已经转换成了最大权闭合图问题。

由于对于任意两个密度不同的子图$A=(V_A,E_A)$和B=(V_B,E_B),不妨设图A的密度大于图B。那么有

因此我们二分的精度可以设为$\frac{1}{|V|^2}$,二分的上界为$|E|$,而二分的下界为$0$,总共二分次数为:

最小费用最大流

每次沿着费用最小的路增广得到的最大流就是最小费用最大流。随着不断增广,最小费用路径的费用和会越来越大。

目前所有通过最小费用路径增广的算法都不具有多项式时间复杂度,其时间复杂度与最大的流量相关联。Codeforces上有相关的讨论

Dijkstra算法优化最小费用最大流

通过最小费用路径增广最小费用最大流算法,一般采用的都是Spfa搜最小费用路径,这样的话时间复杂度应该为$O(VEf)$,其中$f$是最大流。

但是事实上我们可以利用与Johnson算法类似的思想,将所有边权全部修正为非负。

具体做法是这样的,我们先对原始网络跑出没个顶点从源点出发的最短距离(第一次利用Spfa算法跑),之后修正边$(u,v)$的权重为$W(u,v)+D(u)-D(v)$,由最短路的性质知道$D(u)+W(u,v)\geq D(v)$,很显然此时的图中不存在负权边。

现在考虑增广了流后残存网络的变化:新的边加入以及旧的边被删除。

考虑新的边$(v,u)$被加入,这意味着$(u,v)$在该次增广时处于最短路径上,那么就一定有$D(v)=D(u)+W(u,v)$,而$(v,u)$的权重将被修正为$W(v,u)+D(v)-D(u)=0$,即没有负权边加入。

旧的边被删除并不会破坏图中无负权边的性质,可以不用考虑。

因此总的时间复杂度为$O(f(V+E)\log_2V)$,不管咋说,都要比Spfa的版本的好。

最小割树(Gomory-Hu Tree)

强烈推荐一发大佬的博客,我也是看这篇博客学会的。

下面讲一下自己的理解。

假设给定一个拥有$n$个顶点$m$条边的连通无向图$G=(V,E)$,每条边有一个边权,而图上的从$s$到$t$的割就是$E$的一个子集$E'$,使得从$G$中删除所有$E'$的边后,那么$s$与$t$就不再连通。而所有割中割去的边的总权值最小的称为最小割。网络流中证明了最小割恒等于最大流。这里我们记$F(s,t)$表示$(s,t)$的最小割的权值之和。

而$G$的最小割树是一颗拥有$n$个顶点的树$T$,对于$T$的所有边$(u,v)$,一定满足$(u,v)$的权值等于$F(u,v)$,并且从树中删除边$(u,v)$得到的两个连通块,包含$u$的连通块中的顶点集合恰好是$G$删除最小割后,与$u$保持连通的顶点集合,而包含$v$的连通块中的顶点集合恰好是$G$删除最小割后,与$v$保持连通的顶点集合。

很显然我们可以递归构建这样的一颗最小割树,任意选择当前顶点集合中两个不同顶点$u,v$,之后求出最小割$F(u,v)$,往$T$中加入一条边,之后将与$u$保持连通的顶点集合和与$v$保持连通的顶点集合分别递归处理。总的时间复杂度为$O(n^2+nU)$,其中$U$是每次求图$G$最大流的时间复杂度。

下面我们来证明一个重要的一些命题:

命题1:对于最小割树上的两条边$(a,b)$和$(b,c)$,一定满足$F(a,c)\leq \min(F(a,b),F(b,c))$

证明:

这是很显然的,由于从图$G$移除$a$到$b$的最小割后,$c$落在了$b$连通块中,那么一定有$c$与$a$不连通,换句话说,就是$a$到$b$的最小割同时也是$c$与$a$的一个割,由此得到$F(a,c)\leq F(a,b)$,同理可以得到$F(a,c)\leq F(b,c)$。

命题2:对于最小割树上的两条边$(a,b)$和$(b,c)$,一定满足$F(a,c)\geq \min(F(a,b),F(b,c))$

证明:

考虑从图$G$删除$a$与$c$的最小割后,不失一般性假设$b$与$c$连通。那么由于$c$与$b$不连通,因此可以断定$a$与$b$也不连通,即$a$与$c$的最小割同时也是一个$a$与$b$的割,因此可以推出$F(a,c)\geq F(a,b)$。当然如果$b$与$a$连通,那么我们则可以推出$F(a,c)\geq F(b,c)$。

命题4:对于最小割树上的两条边$(a,b)$和$(b,c)$,一定满足$F(a,c)= \min(F(a,b),F(b,c))$

证明:

结合命题1和命题2可以直接得出。

命题5:任意两点$u,v$的最小割$F(u,v)$一定等于最小割树上$u$到$v$的唯一路径中权重最小的边的权重(即最小瓶颈边)

证明:

可以根据树上路径的长度进行归纳法证明。

提供一道BZOJ题目

不过说句实话,因为最小割的时间复杂为$O(n^2+nU)$,而你对所有顶点对直接跑最小割的时间复杂度也只是$O(n^2U)$而已,因此除非遇到非常多的最小割请求,否则最小割树并不是多好的选择。

参考资料