最大流算法

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^-=A^++B^+-(B^+-A^-)=V^+-cut(G')\]

这里$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')$,使得边数与顶点数的比值尽可能大:

\[\max \phantom{1}\frac{|E'|}{|V'|}\]

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

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

\[h(c)=max\{|E'|-c|V'|\Big|G'=(V',E')\subseteq G\}\]

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

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

\[\frac{|E_A|}{|V_A|}-\frac{|E_B|}{|V_B|}=\frac{|E_A||V_B|-|E_B||V_A|}{|V_A||V_B|}\geq \frac{1}{|V_A||V_B|}\geq \frac{1}{|V|^2}\]

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

\[\log_2{\frac{|E|-0}{\frac{1}{|V|^2}}}=O(\log_2|V|)\]

最小费用最大流

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

目前所有通过最小费用路径增广的算法都不具有多项式时间复杂度,其时间复杂度与最大的流量相关联。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的版本的好。

容量缩放+消圈算法

我们知道通过最小费用路增广的最小费用流算法是可以被卡到指数级的,这时候即使只有40个顶点,也是在几秒有限时间内无法算出结果的。

下面讲一个可以在$O(VE^2\log_2U)$时间复杂度内结束的伪多项式时间复杂度的算法。由于实际问题中精度一般有限,因此我们可以认为$\log_2U\leq 60$。当然这个算法只适合用于整数容量(如果是浮点数,那么必须牺牲一些精确度,将其转换为整数,比如乘上一个较大的数,最后再除去)。

下面讲一下具体做法。

首先我们从汇点向源点连一条费用为负无穷,容量为无穷的边。于是这样取到最小费用流的同时也会得到最大流(如果不要求最大流,可以将这条边的费用设为$0$)。

首先我们将所有边的流量设置为0,并将流量上限设置为0。之后我们记所有边最大的容量为$C$,我们枚举一个变量$x$,初始值为$\lfloor \log_2C \rfloor$。

当我们枚举某个$x$的时候,且网络没有负权环。那么我们将所有边的上限翻倍同时将流量翻倍,可以发现网络中依旧不存在负权环。如果某条边的容量的二进制的第$x$位为$1$,那么我们将这条边上限提高$1$。这时候可能会引入负权环,此时负权环一定包含这条边。设这条边为$(u,v)$,在扩容前,我们可以通过Spfa算法找到从$v$到$u$的最短路,长度记做$d(u)$。如果$d(u)+cost(u,v)<0$,这表示是一个负环,我们在负环上跑一单位的流。跑完后,我们可以证明图中不再存在负权环。

因此我们发现每条边最多扩容$\log_2U$次,每次扩容消环的时间复杂度为$O(VE)$,因此总的时间复杂度为$O(VE^2\log_2U)$。

最小割树(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)$而已,因此除非遇到非常多的最小割请求,否则最小割树并不是多好的选择。

分解二分图为多个哈密顿环

给定二分图$G=(V,E)$,其中$V$由两个点集$A$和$B$组成,且所有边的一个端点为$L$中顶点,另外一个端点为$R$中顶点。要求讲二分图分为任意个哈密顿环,要求每个顶点恰好在一个哈密顿环中出现正好一次,其中$1\leq V,E\leq 10^5$。

提供一道题目:SRM788 ParkPlace。

这个问题还是很有趣的。对于二分图中现存的边,我们将它们的容量全部设置为$1$。但是和最大匹配问题不同的是,我们从源点到所有$A$中的元素连一条容量为$2$的边,从$B$中元素到汇点连一条容量为$2$的边。

之后我们考虑存在一种哈密顿环路划分的情况,这时候每个顶点的度数都为$2$,且$A$与$B$的总度数必须相同,即$|A|=|B|$。这时候我们发现必定存在最大流量$2|A|$,我们可以将哈密顿环路转化为一个最大流方案。如果两个顶点$a,b$在某个环路中连续出现,那么我们就将最大流的$(a,b)$边的流量设为$1$。这样就能得到一个最大流了。

同时我们考虑在已知$|A|=|B|$且最大流为$2|A|$的情况。这时候我们发现网络中每个$A,B$集合中所有顶点的度数均为$2$,这时候我们可以将所有的顶点划分为若干个连通块,而一个连通块中所有度数为$2$,意味着这个连通块是一个环。

因此我们只需要跑最大流即可,用Dinic的话时间复杂度为$O(E^{1.5}+V)$。

Dinic解决二层图最大流

我们知道Dinic可以在$O(E\sqrt{V})$时间复杂度内求二分图匹配。但是Dinic还有一种特殊的用法,就是当二分图每个顶点可以匹配多于一个顶点的时候。这时候用最大流表示,就是一个两层的图,第一层与第二层之间有连边,源点与第一层顶点有连边(容量任意),第二层顶点和汇点有连边(容量任意),且第一层和第二层之间的连边的容量都为$1$。这时候根据Karzanov's theorems可以的出Dinic的时间复杂度为$O(E^{1.5})$。(但是我没有找到这个理论的具体出处)。

提供一道需要用到这个性质的题目

最小费用修复网络问题

问题1:给定一个包含$n$个顶点的网络图,顶点$n$是汇点。图中有$m$条单向边,第$i$条边当前的流量为$f_i$,容量为$c_i$。现在希望我们调整每条边的流量和容量,记调整后的流量为$f'_i$,容量为$c'_i$,满足下面条件:

  • $\forall 1\leq i\leq n(0\leq f'_i\leq c'_i)$
  • 每个顶点的入流和出流相等

增大减少第$i$条边的流量的单位费用为$a_i$,增大减少第$i$条边的容量的费用为$b_i$。要求计算最小费用,并且计算最小费用。

其中$c_i,f_i,c'_i,f'_i,a_i,b_i$都为非负整数。

我们考虑原始流为$f$,修正后的流为$f'$,记$\delta=f'-f$。那么可以发现$\delta$是个很特殊的流,我们需要最小化$\delta$的费用,也就是我们的结果。

首先我们加入一个超级源点$s$和超级汇点$t$。

要解决第一个条件,我们考虑第$i$条边$(u_i,v_i)$,我们可以在图中加入4条边。

  • 从$u_i$到$v_i$连一条容量为$\max(c_i-f_i,0)$的费用为$a_i$的边。
  • 从$v_i$到$u_i$连一条容量为$\min(f_i,c_i)$的费用为$a_i$的边。
  • 从$u_i$到$v_i$连一条容量为无穷,费用为$a_i+b_i$的边。
  • 从$v_i$到$u_i$连一条容量为$\max(f_i-c_i,0)$的费用为$a_i-b_i$的边。

这样我们就可以模拟修改流量和容量的操作了。

考虑某个入流为$x$,出流为$y$的顶点$u$,如果$x>y$,则其额外的流为$x-y$。我们需要想办法把它清除掉。做法就是我们从$s$到$u$连一条容量为$x-y$,费用为$0$的边,在最大流的前提下,这条边一定会被流满。同理如果$x\lt y$,其缺少的流为$y-x$,我们需要想办法填补它,做法就是从$u$到$t$连一条容量为$y-x$,费用为$0$的边,在最大流的前提下,这条边会被流满。

之后我们跑出最小费用最大流后,将所有与$s$和$t$相关的边删除后,得到的流就是我们求的$\delta$,费用为我们求的结果。

问题2:给定一个包含$n$个顶点的网络图,其中顶点$1$是源点,顶点$n$是汇点。图中有$m$条单向边,第$i$条边当前的流量为$f_i$,容量为$c_i$。现在希望我们调整每条边的流量和容量,记调整后的流量为$f'_i$,容量为$c'_i$,满足下面条件:

  • $\forall 1\leq i\leq n(0\leq f'_i\leq c'_i)$
  • 除了源点和汇点外,每个顶点的入流和出流相等

增大减少第$i$条边的流量的单位费用为$a_i$,增大减少第$i$条边的容量的费用为$b_i$。要求计算最小费用,并且计算最小费用。

其中$c_i,f_i,c'_i,f'_i,a_i,b_i$都为非负整数。

问题2和问题1的区别仅在于有两个特殊的点(源点和汇点)。如果我们直接在这样的图上跑最小费用最大流,那么由于最终每个顶点都会流量平衡(入流和出流相等),因此会导致所有流都被回退(即总流量为$0$)。解决这个问题的方法就是从顶点$n$到$1$加入一条流量为无穷费用为0的边,这样就能保证不需要回退所有流,就可以达到流量平衡(修正后的总流量会通过这条边发送到顶点$1$)。

提供一道题目

参考资料