最大流算法及其应用

《最大流算法及其应用》由会员分享，可在线阅读，更多相关《最大流算法及其应用（45页珍藏版）》请在装配图网上搜索。

1、2021/3/101最大流算法及其应用最大流算法及其应用2021/3/102提要l网络流相关的一些概念l最大流和最小割问题l最大流算法的应用l总结2021/3/103一、网络流相关的一些概念2021/3/104流网络(Flow Network)l流网络是一个有向图G=(V,E)，其中每条边(u,v)E均有一非负容量c(u,v)0。如果(u,v)E，则假定c(u,v)=0。流网络中有两个特别的顶点：源点源点s和汇点汇点t。2021/3/105图1 一个流网络的例子stv1v4v5v2v3v6352216423142021/3/106流(Flow)lG的流是一个实值函数f，f(u,v)表示顶点u到

2、顶点v的流，它可以为正，为零，也可以为负，且满足下列三个性质：l容量限制容量限制：对所有u,vV，要求f(u,v)c(u,v)。l反对称性反对称性：对所有u,vV，要求f(u,v)=-f(v,u)。l流守恒性流守恒性：对所有u,vV-s,t，要求(,)0v Vf u v2021/3/107流量l整个流网络G的流量：(,)v Vff s v(,)u Vff u t2021/3/108割(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 v2021/3/109残留网络(R

3、esidual Network)l给定一个流网络G=(V,E)和流f，由f压得的G的残留网络Gf=(V,Ef)，定义cf(u,v)为残留网络Gf中边(u,v)的容量。如果弧(u,v)E或弧(v,u)E，则(u,v)Ef，且cf(u,v)=c(u,v)-f(u,v)。在下面的各种概念和方法中，我们只考虑残留网络中容量大于0的弧，但是编程时为了方便还是保留了。2021/3/1010增广路径(Augmenting Path)l对于残留网络Gf中的一条s-t路径p称其为增广路径，定义增广路径p的残留容量为p上弧容量的最小值。后面求最大流要用到增广路径这个概念。2021/3/1011增广(Augment

4、)l对于残留网络Gf中的一条增广路径p，增广的意思就是对于每一条属于p的弧(u,v)，将f(u,v)增加p的残留容量，将f(v,u)减少p的残留容量。这样的话，新的流f仍然满足流的三条性质，并且原流网络的流量|f|增加了。一般来说，增广过后就会修改残留网络，易得对于每一条属于p的弧(u,v)，要将cf(u,v)减去p的残留容量，cf(v,u)加上p的残留容量。（程序实现基本都是通过直接修改残留网络来实现增广的）2021/3/1012二、最大流和最小割问题 2021/3/1013最大流问题l对于一个流网络G=(V,E)，其流量|f|的最大值称为最大流，最大流问题就是求一个流网络的最大流。2021

5、/3/1014增广路定理l当且仅当由当前的流f压得的残留网络Gf中不存在增广路径时，流f的流量|f|达到最大。（证明在此略去，可以参见相关书籍）l根据增广路定理，我们可以设计出最基本的求最大流的方法，一开始将流网络G=(V,E)的流f置为零流，即对于(u,v)E时，f(u,v)=0。然后构建残留网络，寻找增广路径增广，再修改残留网络，重复此过程，直到无法找到增广路径。此方法（之所以不是算法，是因为实现方法很多）称为Ford-Fulkerson方法。2021/3/1015Ford-Fulkerson方法的伪代码lFORD-FULKERSON-METHORD(G,s,t)l1 initialize

6、 flow f to 0l2 while there exists an augmenting path pl3 do augment flow f along pl4 return f 2021/3/1016最小割问题l最小割是指流网络中容量最小的割。lFord-Fulkerson定理（最小割最大流定定理（最小割最大流定理）：理）：在流网络中，最小割的容量等于最大流的流量。（证明也在此略去）l根据这个定理，我们就可以通过求流网络的最大流来得到最小割。2021/3/1017最大流算法l前面所讲的只是求最大流的一种方法，但怎样高效地实现还是一个问题。l这个方法的最大问题就在于怎样快速地找到一条增

7、广路径。当然我们可以用最基本的搜索（DFS或BFS），但是这种方法肯定不够高效，这时我们就需要更高效的算法。l本文将重点介绍一种高效且实用的最大流算法：SAP算法算法（最短增广路算法）。2021/3/1018最短增广路算法l即每次寻找包含弧的个数最少的增广路进行增广，可以证明，此算法最多只需要进行mn/2次增广。并且引入距离标号的概念，可以在O(n)的时间里找到一条最短增广路。最终的时间复杂度为O(n2m)，但在实践中，时间复杂度远远小于理论值（特别是加了优化之后），因此还是很实用的。（此段中n表示顶点数|V|，m表示边数|E|）2021/3/1019距离标号l对于每个顶点i赋予一个非负整数值

8、d(i)来描述i到t的“距离”远近，称它为距离标号，并且满足以下两个条件：ld(t)=0l对于残留网络Gf中的一条弧(i,j)，d(i)d(j)+1。2021/3/1020允许弧和允许路l如果残留网络Gf中的一条弧(i,j)满足d(i)=d(j)+1，我们称(i,j)是允许弧，由允许弧组成的一条s-t路径是允许路。显然，允许路是残留网络Gf中的一条最短增广路。当找不到允许路的时候，我们需要修改某些点的d(i)。2021/3/1021算法基本架构lProcedure Shortest_Augmenting_Path;lVarl lBeginl 预处理流为零流，建立残留网络l 计算距离函数d(i)

9、l/实际上一开始没有必要用BFS计算，清零就行了l i:=s;2021/3/1022l 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 end2021/3/1023l elsel if i出发有弧 thenl d(i)=min d(j)+1|(i,j)在残留网络中l elsel beginl d(i):=n;/禁止以后再考虑顶点il 当is时退回到前一步l end;l end;lEnd;2021/3

10、/1024SAP的优化lSAP算法有两个重要的优化：Gap优化优化和当前弧优化当前弧优化。2021/3/1025Gap优化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，发现没有一个d(j)为k，因此就会尝试去调整d(i)，但是d(i)是单调递增的，只会越来越大，所以k这个空缺便永远不会被补上，也就是说无法再找到增广路径。

11、2021/3/1026当前弧优化l可以注意到一个事实：如果说在某次迭代中从i出发的弧(i,j)不是允许弧，则在顶点i的标号修改之前(i,j)都不可能是允许弧。（因为d(i)不变，d(j)不减且d(i)d(j)+1）这样，在查找允许弧的时候只需要从上一次找到的允许弧开始找。所以我们增加“当前弧”这个数据结构，记录当前顶点找到的允许弧，只有在修改这个顶点标号时才会更改这个顶点的当前弧。2021/3/1027SAP的两个优化效果比较l（程序1：SAP 程序2：SAP+Gap 程序3：SAP+当前弧 程序4：SAP+Gap+当前弧）l测试题目：NOI2006最大获利2021/3/1028比较结果（表中

12、时间单位：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（测试环境：Core 2 Duo E4600 2.4 GHz/2GB）论效果的话，可能G

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

14、点，将每个右边的点连到汇，并把原来的边改为有向的，从左边的点指向右边的点，最后把图中所有弧的容量赋为1，这个流网络的最大流即为原二分图的最大匹配。2021/3/1033图3 新建的流网络（图中弧的容量均为1）st2021/3/1034分析（续）l对于每个左边的点，进去的流量最多只有1；对于每个右边的点，出去的流量最多只有1，所以每个点最多在选中的边里最多出现一次（选中的边即为中间流量为1的弧）。又因为流最大，所以结果就是原二分图的最大二分匹配。l关于二分图的最大二分匹配还有另外一种算法：匈牙利算法，具体的内容可以参阅其他资料。2021/3/1035最小割模型l最小割问题是网络流建模里的一个难点

15、，由于最小割模型在原问题中往往很隐蔽，有时确实需要凭感觉。l看一道比较有难度的例题最大获利（NOI2006第二试）：2021/3/1036最大获利l【问题描述】l新的技术正冲击着手机通讯市场，对于各大运营商来说，这既是机遇，更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜，需要做太多的准备工作，仅就站址选择一项，就需要完成前期市场研究、站址勘测、最优化等项目。l在前期市场调查和站址勘测之后，公司得到了一共N个可以作为通讯信号中转站的地址，而由于这些地址的地理位置差异，在不同的地方建造通讯中转站需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转

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

17、,Bi和Ci描述第i个用户群的信息。l所有变量的含义可以参见题目描述。l【输出格式】l你的程序只要向输出文件输出一个整数，表示公司可以得到的最大净获利。2021/3/1038l【输入样例】l5 5l1 2 3 4 5l1 2 3l2 3 4l1 3 3l1 4 2l4 5 3l【输出样例】l42021/3/1039l【样例说明】l选择建立1、2、3号中转站，则需要投入成本6，获利为10，因此得到最大收益4。l【评分方法】l本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。l【数据规模和约定】l80%的数据中：N200，M1 000。l100%的数据中：N5 000

18、，M50 000，0Ci100，0Pi100。2021/3/1040分析l看到了“最大”这个字眼，很多人便以为此题与最小割没有关系，但实际上不是。由于：l净获利=获益之和-投入成本之和l =所有用户群的获益-（损失用户群的获益+建设中转站的代价）l要使净获利最大，即使（损失用户群的获益+建设中转站的代价）最小，这就将“最大”变成了“最小”。2021/3/1041建模l下面建立流网络，以每一个中转站和用户群为顶点，并增加源和汇。连接源到每个中转站，容量为建设该中转站的代价；连接每个用户群到汇，容量为该用户群的收益；对于每个用户群，连接它的两个相关中转站到这个用户群，容量为。由于割将所有的点分为S

19、和T两个集合，又因为是最小割，所以割的容量必定不会包含中间那些容量为的弧，因此每个用户群及其两个相关的中转站必定在一个集合中。那么T中包含的中转站便是我们选择建设的，S中包含的用户群即为放弃的用户群。割的容量为源到所有T中包含的中转站的建设费用和加上S中包含的所有用户的获益和。又因为割的容量最小，所以结果最优。2021/3/1042图4 样例建成的流网络（中间弧的容量均为）st12345343232021/3/1043实现l最后再观察数据范围，可得流网络的点数最多会有55002（5000+50000+2）个，一般的最大流算法基本都是会超时的（虽然时限有2s），但是用邻接表的SAP加上Gap和当前弧优化是可以轻松AC的。2021/3/1044四、总结l网络流算法越来越在信息学竞赛中广泛应用，而且网络流的建模一直是一个难点。在平时的练习中，我们还是要多做题，多见一些常见的模型，这样才能在竞赛时很快想起来网络流的模型和算法。l总之，在学习中多练习和总结还是最重要的，只有这样才能更快地提高水平。2021/3/1045