最大流算法

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不相连。这里建模网络的时候权重为w的无向边应该表示为两条反向的容量为w的有向边（或一个容量为2w而流量为w的边）。

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

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

题目1：给定一个包含n个顶点m条边的无向图，每条边都有删除成本（正数），希望删除一组总成本最小的边，使得顶点1和n不连通。

这是一个典型的最小割问题，对于每条边(u,v)，记其费用为c，我们在网络中加入一条容量为c的双向边（注意也需要是双向的）。之后找到最小割即可。

题目2：给定一个包含n个顶点m条边的无向图。每个顶点都有删除成本，希望删除一组总成本最小的边，使得顶点1和n不连通。保证顶点1和n之间没有边。

我们把每个顶点i拆分成Xi和Yi两个顶点，两个顶点之间加入一条容量为删除成本的双向边。这样删点可以转换为删除边。之后对于每条图中的双向边(u,v)，其中u,v≠1,n，我们对应加入一条Yu到Xv以及从Yv到Xu的容量为无穷的单向边。对于边(1,u)，我们在源点到Xu之间加入一条容量为无穷的单向边，而对于边(v,n)，我们在Yv向汇点连一条容量为无穷的单向边。

题目3：给定一个流网络，其中除了源点s和汇点t外还有n个顶点，源点到第i个顶点有一条容量为ai的边，而第i个顶点到汇点有一条容量为bi的边，且对于任意i<j，存在一条从i到j的容量为c的边。要求计算最大流。

提供一道题目。

这个问题用最大流求，时间复杂度至少为O(n3)。但是如果用最小割求，则可以优化到O(n2)。

具体做法是记dp(i,j)表示前i个顶点，割后属于S的顶点有j个的最小割边费用。可以发现这个DP的转移是O(1)的，因此时间复杂度为O(n2)。

平面图最小割

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

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

提供一道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)∈E，有u∈U⇒v∈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∩V一定是一个闭合图，否则就存在这样一条边(u,v)∈E，u∈X且v∈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：给定一个依赖图（无环），但是所有依赖关系都是带权的，即(a,b,c)表示a依赖b，但是如果不执行b，也可以通过负担一个指定的惩罚c来继续执行a。现在求最大闭合子图。

在我们将依赖图转换为网络流的时候，针对依赖(a,b,c)，我们从a向b连一条容量为c的边而非容量无穷即可。

之后直接通过最大流找最大闭合子图。

提供一道题目。

独占路问题

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

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

时间复杂度为O(min(n2m,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′)，使得边数与顶点数的比值尽可能大：

max1|E′||V′|

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

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

h(c)=max{|E′|−c|V′||G′=(V′,E′)⊆G}

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

由于对于任意两个密度不同的子图A=(VA,EA)和B=(VB,EB)，不妨设图A的密度大于图B。那么有

|EA||VA|−|EB||VB|=|EA||VB|−|EB||VA||VA||VB|≥1|VA||VB|≥1|V|2

因此我们二分的精度可以设为1|V|2，二分的上界为|E|，而二分的下界为0，总共二分次数为:

log2|E|−01|V|2=O(log2|V|)

最小费用最大流

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

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

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

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

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

具体做法是这样的，我们先对原始网络跑出没个顶点从源点出发的最短距离（第一次利用Spfa算法跑），之后修正边(u,v)的权重为W(u,v)+D(u)−D(v)，由最短路的性质知道D(u)+W(u,v)≥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)log2V)，不管咋说，都要比Spfa的版本的好。

容量缩放+消圈算法

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

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

下面讲一下具体做法。

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

首先我们将所有边的流量设置为0，并将流量上限设置为0。之后我们记所有边最大的容量为C，我们枚举一个变量x，初始值为⌊log2C⌋。

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

因此我们发现每条边最多扩容log2U次，每次扩容消环的时间复杂度为O(VE)，因此总的时间复杂度为O(VE2log2U)。

最小割树(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(n2+nU)，其中U是每次求图G最大流的时间复杂度。

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

命题1：对于最小割树上的两条边(a,b)和(b,c)，一定满足F(a,c)≤min(F(a,b),F(b,c))。

证明：

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

命题2：对于最小割树上的两条边(a,b)和(b,c)，一定满足F(a,c)≥min(F(a,b),F(b,c))。

证明：

考虑从图G删除a与c的最小割后，不失一般性假设b与c连通。那么由于c与b不连通，因此可以断定a与b也不连通，即a与c的最小割同时也是一个a与b的割，因此可以推出F(a,c)≥F(a,b)。当然如果b与a连通，那么我们则可以推出F(a,c)≥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(n2+nU)，而你对所有顶点对直接跑最小割的时间复杂度也只是O(n2U)而已，因此除非遇到非常多的最小割请求，否则最小割树并不是多好的选择。

Dinic解决单位图最大流

对于单位图，即除了源点和汇点外，其余顶点的要么只有一条入边且容量为1，要么只有一条出边且容量为1，其余边的容量任意，则Dinic可以在O(V1/2E)时间复杂度内计算最大流。

如果能保证所有网络中边的容量都是1，那么时间复杂度可以约束到O(min(V2/3,E1/2)E)。

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

最小费用修复网络问题

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

  • ∀1≤i≤n(0≤f′i≤c′i)
  • 每个顶点的入流和出流相等

增大减少第i条边的流量的单位费用为ai，增大减少第i条边的容量的费用为bi。要求计算最小费用，并且计算最小费用。

其中ci,fi,c′i,f′i,ai,bi都为非负整数。

我们考虑原始流为f，修正后的流为f′，记δ=f′−f。那么可以发现δ是个很特殊的流，我们需要最小化δ的费用，也就是我们的结果。

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

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

  • 从ui到vi连一条容量为max(ci−fi,0)的费用为ai的边。
  • 从vi到ui连一条容量为min(fi,ci)的费用为ai的边。
  • 从ui到vi连一条容量为无穷，费用为ai+bi的边。
  • 从vi到ui连一条容量为max(fi−ci,0)的费用为ai−bi的边。

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

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

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

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

  • ∀1≤i≤n(0≤f′i≤c′i)
  • 除了源点和汇点外，每个顶点的入流和出流相等

增大减少第i条边的流量的单位费用为ai，增大减少第i条边的容量的费用为bi。要求计算最小费用，并且计算最小费用。

其中ci,fi,c′i,f′i,ai,bi都为非负整数。

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

提供一道题目。

费用流解决二分图标签问题

最近遇到了一些标签问题，所谓的标签问题是，给定两组非负变量x1,…,xn以及y1,…,ym，存在一些三元组(i,j,c)，要求xi+yj≥c。要求找出一组可行解，存在多个可行解的情况下，要求∑ni=1xi+∑mi=1yi最小化。

这个问题实际上可以使用Kuhn-Munkres算法O(max(n,m)3)计算得到。当然这个方案又两个问题，一个就是对于稀疏图效率较低，第二个问题是不能进一步扩展。即我们的约束条件修改为xi+yj≤c，而总和∑ni=1xi+∑mi=1yi的要求变成最大化。这个就没法用KM算法来求解了（不相信可以试一下XD）。

我们先将问题描述为线性规划形式：

min∑ixi+∑jyjst.xi+yj≥ci,jx,y≥0

再考虑它的对偶形式：

max∑(i,j)∈Eci,jzi,jst.∑(i,j)∈Ezi,j≤1x,y≥0

上面对偶形式实际上描述的是最大权二分图匹配，而利用Dijkstra优化的费用流在稀疏图上实际上可以跑到O(VElog2V)的时间复杂度。需要注意系数矩阵实际上是无向二分图的关联矩阵，是全幺模矩阵，因此线性规划的结果一定是整数。

再考虑扩展问题的线性规划形式：

max∑ixi+∑jyjst.xi+yj≤ci,jx,y≥0

其对偶形式为：

min∑(i,j)∈Eci,jzi,jst.∑(i,j)∈Ezi,j≥1x,y≥0

上面描述的实际上是最小权边覆盖问题，我们可以建模费用流来求解。需要注意的是系数矩阵实际上是无向二分图的关联矩阵，是全幺模矩阵，因此线性规划的结果一定是整数。我们可以用线性规划求解。

提供一些题目：

参考资料