最大流算法及其应用

1、最大流算法及其应用最大流算法及其应用提要l网络流相关的一些概念l最大流和最小割问题l最大流算法的应用l总结一、网络流相关的一些概念流网络 (Flow Network)l流网络是一个有向图G=(V,E)，其中每条边(u,v)E均有一非负容量c(u,v)0。如果(u,v)E，则假定c(u,v)=0。流网络中有两个特别的顶点：源点源点s和汇点汇点t。图1 一个流网络的例子stv1v4v5v2v3v635221642314流 (Flow) lG的流是一个实值函数f，f(u,v)表示顶点u到顶点v的流，它可以为正，为零，也可以为负，且满足下列三个性质：l容量限制容量限制：对所有u,vV，要求f(u,v)

2、c(u,v)。l反对称性反对称性：对所有u,vV ，要求f(u,v)=-f(v,u)。l流守恒性流守恒性：对所有u,vV-s,t，要求( , )0v Vf u v流量l整个流网络G的流量：( , )v Vff s v( , )u Vff u t割 (Cut) l流网络G=(V,E)的割(S,T)将划分成S和T=V-S两部分，使得sS，tT。定义割(S,T)的容量为c(S,T)，则：,( , )( , )u S v Tc S Tc u v残留网络 (Residual Network) l给定一个流网络G=(V,E)和流f，由f压得的G的残留网络Gf=(V,Ef)，定义cf(u,v)为残留网络Gf

3、中边(u,v)的容量。如果弧(u,v)E或弧(v,u)E，则(u,v)Ef，且cf(u,v) =c(u,v)-f(u,v)。在下面的各种概念和方法中，我们只考虑残留网络中容量大于0的弧，但是编程时为了方便还是保留了。增广路径 (Augmenting Path)l对于残留网络Gf中的一条s-t路径p称其为增广路径，定义增广路径p的残留容量为p上弧容量的最小值。后面求最大流要用到增广路径这个概念。增广 (Augment)l对于残留网络Gf中的一条增广路径p，增广的意思就是对于每一条属于p的弧(u,v)，将f(u,v)增加p的残留容量，将f(v,u)减少p的残留容量。这样的话，新的流f仍然满足流的三

4、条性质，并且原流网络的流量|f|增加了。一般来说，增广过后就会修改残留网络，易得对于每一条属于p的弧(u,v)，要将cf(u,v)减去p的残留容量， cf(v,u)加上p的残留容量。（程序实现基本都是通过直接修改残留网络来实现增广的）二、最大流和最小割问题 最大流问题l对于一个流网络G=(V,E)，其流量|f|的最大值称为最大流，最大流问题就是求一个流网络的最大流。增广路定理l 当且仅当由当前的流f压得的残留网络Gf中不存在增广路径时，流f的流量|f|达到最大。（证明在此略去，可以参见相关书籍）l 根据增广路定理，我们可以设计出最基本的求最大流的方法，一开始将流网络G=(V,E)的流f置为零流

5、，即对于(u,v)E时，f(u,v)=0。然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。此方法（之所以不是算法，是因为实现方法很多）称为Ford-Fulkerson方法。Ford-Fulkerson方法的伪代码lFORD-FULKERSON-METHORD (G, s, t)l1 initialize flow f to 0l2 while there exists an augmenting path pl3 do augment flow f along pl4 return f 最小割问题l最小割是指流网络中容量最小的割。lFord-Fulkers

6、on定理（最小割最大流定定理（最小割最大流定理）：理）：在流网络中，最小割的容量等于最大流的流量。（证明也在此略去）l根据这个定理，我们就可以通过求流网络的最大流来得到最小割。最大流算法l前面所讲的只是求最大流的一种方法，但怎样高效地实现还是一个问题。l这个方法的最大问题就在于怎样快速地找到一条增广路径。当然我们可以用最基本的搜索（DFS或BFS），但是这种方法肯定不够高效，这时我们就需要更高效的算法。l本文将重点介绍一种高效且实用的最大流算法：SAP算法算法（最短增广路算法）。最短增广路算法l即每次寻找包含弧的个数最少的增广路进行增广，可以证明，此算法最多只需要进行mn/2次增广。并且引入距

7、离标号的概念，可以在O(n)的时间里找到一条最短增广路。最终的时间复杂度为O(n2m)，但在实践中，时间复杂度远远小于理论值（特别是加了优化之后），因此还是很实用的。（此段中n表示顶点数|V|，m表示边数|E|）距离标号l对于每个顶点i赋予一个非负整数值d(i)来描述i到t的“距离”远近，称它为距离标号，并且满足以下两个条件：ld(t)=0l对于残留网络Gf中的一条弧(i,j)，d(i)d(j)+1。 允许弧和允许路l如果残留网络Gf中的一条弧(i,j)满足d(i)=d(j)+1，我们称(i,j)是允许弧，由允许弧组成的一条s-t路径是允许路。显然，允许路是残留网络Gf中的一条最短增广路。当找

8、不到允许路的时候，我们需要修改某些点的d(i)。算法基本架构l Procedure Shortest_Augmenting_Path;l Varl l Beginl 预处理流为零流，建立残留网络l 计算距离函数d(i)l /实际上一开始没有必要用BFS计算，清零就行了l i:=s;l while d(s)n dol beginl if i出发有允许弧(i,j) thenl beginl 记录j在允许路上的前驱结点il i:=j;l if i=t thenl beginl 沿着增广路增广，修改残留网络l i:=s;l end;l endl elsel if i出发有弧 thenl d(i)=mi

9、n d(j)+1 | (i,j)在残留网络中l elsel beginl d(i):=n; /禁止以后再考虑顶点il 当is时退回到前一步l end;l end;l End;SAP的优化lSAP算法有两个重要的优化：Gap优化优化和当前弧优化当前弧优化。Gap优化l 我们可以注意到由于残留网络的修改只会使d(i)越来越大（因为修改前d(i)d(j)+1，而修改后会存在d(i)=d(j)+1，因此变大了），所以说d(i)是单调递增的，这就提示我们，如果d函数出现了“断层”，即没有d(i)=k，而有d(i)=1，这时候必定无法再找到增广路径。我们可以这么想，现在的i满足d(i)=k+1，发现没有一

10、个d(j)为k，因此就会尝试去调整d(i)，但是d(i)是单调递增的，只会越来越大，所以k这个空缺便永远不会被补上，也就是说无法再找到增广路径。当前弧优化l可以注意到一个事实：如果说在某次迭代中从i出发的弧(i,j)不是允许弧，则在顶点i的标号修改之前(i,j)都不可能是允许弧。（因为d(i)不变，d(j)不减且d(i)d(j)+1）这样，在查找允许弧的时候只需要从上一次找到的允许弧开始找。所以我们增加“当前弧”这个数据结构，记录当前顶点找到的允许弧，只有在修改这个顶点标号时才会更改这个顶点的当前弧。SAP的两个优化效果比较l（程序1：SAP 程序2：SAP+Gap 程序3：SAP+当前弧 程

11、序4：SAP+Gap+当前弧）l测试题目：NOI2006最大获利比较结果（表中时间单位：s）测试点测试点1 1测试点测试点2 2测试点测试点3 3测试点测试点4 4测试点测试点5 5测试点测试点6 6测试点测试点7 7测试点测试点8 8测试点测试点9 9程序程序1 10.010.040.060.040.060.060.10TLETLE程序程序2 20.020.020.020.020.010.010.021.621.64程序程序3 30.020.020.030.030.040.030.05TLETLE程序程序4 40.010.010.020.020.020.020.010.150.15（测试环境

12、：Core 2 Duo E4600 2.4 GHz / 2GB）论效果的话，可能Gap优化占了上风，但是想要获得最佳效果，还是要把两种优化结合起来使用的。三、最大流算法的应用最大流模型l一个典型的最大流模型就是二分图的最大二分匹配。l二分图G=(X,Y,E)，其中X和Y是两个不相交的点集，并且对于每对(u,v)E，uX且vY。二分图的最大二分匹配问题就是从E中选择一些边，使得每个点最多在选择的边里出现一次，问最多能选多少条边。图2 一个二分图的例子及其最大匹配（实线表示选中的边，虚线表示未选中的边）分析l实际上我们可以将二分图的最大匹配问题转换为最大流问题。增加源和汇，将源连到每个左边的点，将

13、每个右边的点连到汇，并把原来的边改为有向的，从左边的点指向右边的点，最后把图中所有弧的容量赋为1，这个流网络的最大流即为原二分图的最大匹配。图3 新建的流网络（图中弧的容量均为1）st分析（续）l对于每个左边的点，进去的流量最多只有1；对于每个右边的点，出去的流量最多只有1，所以每个点最多在选中的边里最多出现一次（选中的边即为中间流量为1的弧）。又因为流最大，所以结果就是原二分图的最大二分匹配。l关于二分图的最大二分匹配还有另外一种算法：匈牙利算法，具体的内容可以参阅其他资料。最小割模型l最小割问题是网络流建模里的一个难点，由于最小割模型在原问题中往往很隐蔽，有时确实需要凭感觉。l看一道比较有

14、难度的例题最大获利（NOI2006第二试）：最大获利l 【问题描述】l 新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。l 在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要的成本为Pi（1iN）。l 另外公司调查得出了所有期望中的用户群，一共M个

15、。关于第i个用户群的信息概括为Ai, Bi和Ci：这些用户会使用中转站Ai和中转站Bi进行通讯，公司可以获益Ci。（1iM, 1Ai, BiN）l THU集团的CS&T公司可以有选择的建立一些中转站（投入成本），为一些用户提供服务并获得收益（获益之和）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利 = 获益之和 - 投入成本之和）l 【输入格式】l 输入文件中第一行有两个正整数N和M 。l 第二行中有N个整数描述每一个通讯中转站的建立成本，依次为P1, P2, , PN 。l 以下M行，第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的信息。l 所有变量的

16、含义可以参见题目描述。l 【输出格式】l 你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。l 【输入样例】l 5 5l 1 2 3 4 5l 1 2 3l 2 3 4l 1 3 3l 1 4 2l 4 5 3l 【输出样例】l 4l 【样例说明】l 选择建立1、2、3号中转站，则需要投入成本6，获利为10，因此得到最大收益4。l 【评分方法】l 本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。l 【数据规模和约定】l 80%的数据中：N200，M1 000。l 100%的数据中：N5 000，M50 000，0Ci100，0Pi100。分析l看

17、到了“最大”这个字眼，很多人便以为此题与最小割没有关系，但实际上不是。由于：l净获利 = 获益之和 - 投入成本之和l = 所有用户群的获益 - （损失用户群的获益 + 建设中转站的代价）l要使净获利最大，即使（损失用户群的获益 + 建设中转站的代价）最小，这就将“最大”变成了“最小”。建模l 下面建立流网络，以每一个中转站和用户群为顶点，并增加源和汇。连接源到每个中转站，容量为建设该中转站的代价；连接每个用户群到汇，容量为该用户群的收益；对于每个用户群，连接它的两个相关中转站到这个用户群，容量为。由于割将所有的点分为S和T两个集合，又因为是最小割，所以割的容量必定不会包含中间那些容量为的弧，因此每个用户群及其两个相关的中转站必定在一个集合中。那么T中包含的中转站便是我们选择建设的，S中包含的用户群即为放弃的用户群。割的容量为源到所有T中包含的中转站的建设费用和加上S中包含的所有用户的获益和。又因为割