网络流算法介绍课件.ppt

1、网络算法介绍PPT网络流算法介绍1.基本概念2.最大流问题求解3.二分图匹配4.二分图最佳匹配关键词：源点、源点、汇点、汇点、容量、容量、流量、流量、残量、残量、费用、费用、增广路径增广路径网络流问题类比：求最短路径把实际问题的道路地图抽象为有向图，然后用一定算法求解最短路径。我们也可以将一个有向图看作一个流网络来解决另一类型的问题。匹配问题、运输问题、任务分配问题。流网络定义（Flow Network）nV表示整个图中的所有结点的集合.nE表示整个图中所有边的集合.nG=(V,E),表示整个有向图.ns表示网络的源点,t表示网络的汇点.n对于每条边(u,v),有一个容量c(u,v)(c(u,

2、v)=0)n如果c(u,v)=0，则表示(u,v)不在网络中。n如果原网络中不存在边(u,v)，则令c(u,v)=0n对于每条边(u,v),有一个流量f(u,v).流网络示例水源水源源点源点S蓄水池蓄水池汇点汇点T水管水管/边边流速限制流速限制容量容量c流速流速/流量流量f网络流三个性质n容量限制：f(u,v)=c(u,v)n对称性：f(u,v)=-f(v,u)n收支平衡:对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。只要满足这三个性质只要满足这三个性质,就是一个合法的网络流就是一个合法的网络流.网络的流量、最大流一个合法的网络流量|f|定义为：n从源点流出的流量

3、f(s,v)n流向汇点的流量 f(v,t)n|f|的最大值表示为最大流流网络示例收支平衡容量限制f(v4,v6)=-f(v6,v4)=1f(v6,v4)图中不给出网络的流量|f|=5+3=8或等于5+2+1(汇点处)0=|f|=最大流残量网络n对于网络中的每一条边，计算容量与流量的差即表示为残量。nR(u,v)=C(u,v)F(u,v)n形象的说，一条边的残量即为该边还能流过的流量。残量网络举例v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原网络残量网络残量网络n从残量网络中可以清楚地看到：n因为存在边(s,v2)=3,则知道从S到v2还可以再增加2单位

4、的流量；n因为存在边(v1,t)=2,则从v1到t还可以再增加2单位的流量。v1tsv2232422后向弧n其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。n但是从v1到s和原网络中的弧的方向相反。这样的弧称为后向弧。n问题：有必要建后向弧线？tsv232422v1为什么要建立后向弧n在寻找最大流的过程中，有些弧的选择一开始可能就是错误的。n所以在路径中加上后向弧，作为标记。n当发现了另一条可增广的路径是并包含后向弧，意味这条路径对以前对这条弧顶选择进行取消n后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为增广路径n在残量网络中，从源点S

5、出发到汇点T的一条路径。n增广路径上的最小残量表示该网络还可增加的额外流量。点集间的流量定义点集间的流量：f(X,Y)=f(x,y)则有：f(X,X)=0 (流的对称性)f(X,Y)=-f(Y,X)(流的对称性)f(XY,Z)=f(X,Z)+f(Y,Z)f(X,YZ)=f(X,Y)+f(X,Z)xX yY点集间的流量n不包含s,t的点集，与它关联的边上的流量和为零证明：f(X,V)=f(x,v)=0(流量收支平衡)=0 xXvVxX网络中的割n割（S,T）由两个点集S,T组成，满足1、S+T=V2、源点在S集合中3、汇点在T集合中4、f(S,T)表示割的流量5、c(S,T)表示割的容量最小切割

6、时使c(S,T)最小的切割割的流量n任意割的流量等于网络的流量证明：f(S,T)=f(S,V)f(S,S)=f(S,V)+0 =f(s,V)+f(S-s,V)=f(s,V)+0 =|f|割的流量n网络的流量小等于任意割的容量证明：|f|=f(S,T)=f(x,y)2n反证法n假设残量网络中还有增广路径，n增广路径上的流量至少为1n由该路径增广后的流量fn与f是最大流矛盾2 3n此时的残量网络中不存在s-t通路n定义S为s可达的点集n定义T为可达t的点集n显然ST=Vn(S,T)中所有弧都满载，否则残量网络将不为0，使s-t有通路n所以|f|=c(S,T)3 1n由|f|3的证明给出了从最大流构

7、造最小割的过程，即求出s的可达点集S，再令T=V-S求最大流的增广路算法n每次用BFS找一条最短的增广路径；n然后沿着这条路径修改流量值（实际修改的是残量网络的边权）。路径上的后向弧+流量值路径上的前向弧-流量值n当没有增广路时，算法停止，此时的流就是最大流。最大流例题BOJ1154n典型的最大流问题n已知网络容量,求最大流量n根据题意构图如下:1为源点,M为汇点.容量为题目已知给出,可能的情况是相同两个结点之间有多条水渠,将它们累加即可.初始化流量网络为0,则残量网络即初始为容量网络.n算法流程:构图-求最大流-输出最大流最大流例题BOJ1154n寻找增广路nbool findload()n

8、n memset(visited,0,sizeof(visited);n head=tail=0;n queuetail+=s;n while(head tail)n n j=queuehead+;n for(i=1;i 0)/cap为容量,本题可以直接表示为残量n n prei=j;/路径标志n visitedi=1;n if(i=t)return true;/找到s-t通路n queuetail+=i;n n return false;n最大流例题BOJ1154n求最大流nint maxflow()nn int i,j,flow=0,min;/min为增广路径上的瓶颈流量;flow网络最大

9、流n while(findload()n n min=0 x7ffffff;n for(i=t;i!=s;i=prei)n min 0的pillars拆开,有L的点由源点向其引一条边,边容量为1,能跳出边界的点向汇点引边,边容量为无穷.n其他题目:pku 3498Cable TV Network n题意:一个无向图,问去掉几个点使得其不连通.n思路:最小点割集,根据最小割最大流定理求解.拆点,求最大流.因为此题没有明确的源点和汇点,所以要枚举源点和汇点,然后求最大流,最大流的最小值就是最小割的最小值.n其他题目：POJ3469 二分图n二分图作为流网络的一个特例，我们既可以特别去讨论它，也可以

10、从网络流的角度来理解它。n定义：二分图又称二部图，它是一个无向图，图的顶点分成两个不相交的点集X,Y.对于图中任意一条边的两端点分别来自不同点集。112233445二分图匹配n给定二分图G，在G的子图M中，M的任意两条边都不共点，则称M为G图的一个匹配。nM中边数最大的子集称为G的最大匹配。n如果在最大匹配中，边涵盖了图中所有的点，则这样的匹配为完美匹配。匈牙利算法n实际上它也是一种不断寻找增广路径的算法n增广路径定义：若path是图G中一条连通两个未匹配顶点(分别属于X,Y)的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在Path上交替出现，则称Path为相对于M的一条增广路径。二

11、分图增广路n由增广路定义可以得出：1、path的长度必为奇数，且第一条边和最后一条边为不匹配边。2、path经过路径取反操作以后，得到比当前更大的匹配。3、当找不到增广路径时候，得到的匹配即为最大匹配。与增广路求最大流算法很类似最大流和二分图匹配n实际上二分图可以改造成一个流网络n把X，Y的边改成从X到Y的有向边，并赋值为1，表示从X到Y容量为1。n添加源点s，s到X部每个点的容量都为1。n添加汇点t，Y到t部每个点的容量都为1。n以此建立的流网络求得到最大流，即为原二分图中的最大匹配数。最大流和二分图匹配n对上述的流网络求最大流的增广路算法我们已经了解了。n每次找增广路时必然是以条从s到t的

12、通路，除去s到X,Y到t两条边，剩下的边必然是在原二分图中交替前进。n前向弧表示尚未匹配的边n后向弧表示已经匹配的边n路径取反操作实际上是更新流量操作二分图匹配的构图n首先划分“对立”的两个集合n明确每个匹配关系的含义n明确最大匹配的意义n从最大流的构图方法来入手二分图匹配例题BOJ1155n中文题目,题意好理解n构图:考虑将墙面看成一个国际象棋的棋盘,那么每块瓷砖贴在棋盘上必然占一格白格和一格黑格.n用棋盘的黑色格子表示二分图X部n用棋盘的黑色格子表示二分图Y部n相邻的格子用一条边连接二分图匹配例题BOJ1155n找增广路径nint path(int v)/从X部的V点找增广路径nnfor(

13、int i=1;i=m;i+)nnif(gvi&!visitedi)/找到未匹配边nnvisitedi=true;nif(matchi=-1|path(matchi)=1)nnmatchi=v;/路径取反操作nreturn 1;nnnnreturn 0;n二分图匹配例题BOJ1155n求最大匹配n cnt=0;/最大匹配数 memset(match,-1,sizeof(match);n for(i=1;i=wij;n对于所有边e(i,j)在M中，都有lxi+lyj=wij;n则M是G的最佳匹配二分图最佳匹配n先将一个未被匹配的顶点u做一次增广路，记下哪些结点被访问那些结点没有被访问。n求出d=

14、minlxi+lyj-wi,j其中i结点被访问，j结点没有被访问。n调整lx和ly：对于访问过的x顶点，将它的可行标减去d，访问过的y顶点，将它的可行标增加d。n修改后的顶标仍是可行顶标，原来的匹配M仍然存在，相等子图中至少出现了一条不属于M的边，所以造成M的逐渐增广。算法流程n(1)初始化可行顶标的值n(2)用匈牙利算法寻找完备匹配n(3)若未找到完备匹配则修改可行顶标的值n(4)重复(2)(3)直到找到相等子图的完备匹配为止二分图最佳匹配例题BOJ1080n题目意思非常清晰n构图非常明确,工作为X,人为YnX到Y的权值已知n求X到Y的最小匹配n把X到Y的劝值改为负数,求最佳匹配后,再取负数

15、,得到的就是最小匹配值.二分图最佳匹配例题BOJ1080n找增广路径nint find(int v)nn int i,tmp;n xv=1;n for(i=0;i n;i+)n if(!yi&lxv+lyi=mapvi)n n tmp=matchi;matchi=v;n yi=1;n if(tmp=-1|find(tmp)n return 1;n matchi=tmp;n n return 0;n二分图最佳匹配例题BOJ1080nint KM()nn int i,j,k,d,ans;n for(k=0;k n;k+)n while(1)n n memset(x,0,sizeof(x);n me

16、mset(y,0,sizeof(y);n if(find(k)break;/找完美匹配子图 n for(d=MAX,i=0;i n;i+)n if(xi)n for(j=0;j n;j+)n if(!yj)d?=lxi+lyj-mapij;n for(i=0;i n;i+)n n if(xi)lxi-=d;n if(yi)lyi+=d;n n n for(ans=0,i=0;i n;i+)ans+=mapmatchii;nreturn ans;n/*可行顶标ly记为0，lx记为与x相连的边的权最大值*/memset(ly,0,sizeof(ly);memset(match,-1,sizeof(match);for(i=0;i n;i+)lxi=-MAX;for(j=0;j?=mapij;总结n网络流模型可以用来解决很多关于分配求最优值得问题，它的最大流，最小费用最大流求解算法我们已经大概了解。n在更多的实际问题中，网络流模型的建立往往是难点。n巧妙的建立一个模型往往能诞生一个优质的算法。Thank you!