网络流算法专题.pptx

会计学1网络流算法专题网络流算法专题运输网络运输网络 现在想将一些物资从现在想将一些物资从S S运抵运抵T T，必须经过一些中转站。连接中转站的是公路，每条，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。公路都有最大运载量。每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S S运抵运抵T T？4248473 621STV1V2V3V4公路运输图公路运输图第1页/共52页基本概念基本概念n n这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。n n若有向图G=(V,E)满足下列条件：1.1.有且仅有一个顶点有且仅有一个顶点S S，它的入度，它的入度为零，即为零，即d-(S)=0d-(S)=0，这个顶点，这个顶点S S便便称为源点，或称为发点。称为源点，或称为发点。2.2.有且仅有一个顶点有且仅有一个顶点T T，它的出度，它的出度为零，即为零，即d+(T)=0d+(T)=0，这个顶点，这个顶点T T便称为汇点，或称为收点。便称为汇点，或称为收点。3.3.每一条弧都有非负数，叫做该边每一条弧都有非负数，叫做该边的容量。边的容量。边(vi,vj)(vi,vj)的容量用的容量用cijcij表表示。示。n n则称之为网络流图，记为G=(V,E,C)第2页/共52页可行流可行流可行流可行流对于网络流图对于网络流图GG，每一条弧，每一条弧(i,j)(i,j)都给定一个非负数都给定一个非负数fijfij，这一组数满足，这一组数满足下列三条件时称为这网络的可行流，用下列三条件时称为这网络的可行流，用f f表示它。表示它。1.1.每一条弧每一条弧(i,j)(i,j)有有f fij ijCCij ij2.2.流量平衡流量平衡除源点除源点S S和汇点和汇点T T以外的所有的点以外的所有的点vi vi，恒有：，恒有：j j(f(fij ij)=k k(f(fjk jk)该等式说明中间点该等式说明中间点vi vi的流量守恒，输入与输出量相等。的流量守恒，输入与输出量相等。3.3.对于源点对于源点S S和汇点和汇点T T有有 ，i i(f(fSi Si)=j j(f(fjTjT)=V()=V(f f)第3页/共52页可增广路可增广路 n n给定一个可行流给定一个可行流f=ff=fij ij。若。若f fij ij=C=Cij ij，称，称为饱和弧；为饱和弧；否则称否则称为非饱和弧。若为非饱和弧。若fij=0fij=0，称，称为零流为零流弧；否则称弧；否则称为非零流弧。为非零流弧。n n定义一条道路定义一条道路P P，起点是，起点是S S、终点是、终点是T T。把。把P P上所有与上所有与P P方方向一致的弧定义为正向弧，正向弧的全体记为向一致的弧定义为正向弧，正向弧的全体记为P+P+；把；把P P上所有与上所有与P P方向相悖的弧定义为反向弧，反向弧的全体记方向相悖的弧定义为反向弧，反向弧的全体记为为P-P-。n n譬如在图中，譬如在图中，P=(S,V1,V2,V3,V4,T)P=(S,V1,V2,V3,V4,T)，那么，那么P+=,P+=,P-=P-=n n给定一个可行流给定一个可行流f f，P P是从是从S S到到T T的一条道路，如果满足：的一条道路，如果满足：f fij ij是非饱和流，并且是非饱和流，并且 P+,f P+,fij ij是非零流，并且是非零流，并且 P-P-那么就称那么就称P P是是f f的一条的一条可增广路可增广路可增广路可增广路。之所以称作。之所以称作“可增广可增广”，是因为可改进路上弧的流量通过一定的规则修改，可，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。以令整个流量放大。第4页/共52页剩余图剩余图(残余网络残余网络)n n剩余图G=(V,E)n n流量网络G=(V,E)中，对于任意一条边(a,b)，若n nflow(a,b)0n n则(a,b)E可以沿着a-b方向增广第5页/共52页l剩余图中，从源点到汇点的每一条路径都对应一条增广路Capacity=5Capacity=6Capacity=2Flow=2Flow=2Flow=2有向图32224剩余图l剩余图中，每条边都可以沿其方向增广剩余图的权值代表能沿边增广的大小第6页/共52页n nG=(V,E,C)是已知的网络流图，设U是V的一个子集，W=VU，满足S U，TW。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。n n对于弧尾在U，弧头在W的弧所构成的集合称之为割切割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：割切割切 第7页/共52页割切示例割切示例v上例中，令U=S,V1，则W=V2,V3,V4,T，那么，vC(U,W)=+=8+4+4+1=17第8页/共52页流量算法的基本理论流量算法的基本理论n n定理定理1：对于已知的网络流图，：对于已知的网络流图，设任意一可行流为设任意一可行流为f，任意一割，任意一割切为切为(U,W)，必有：，必有：V(f)C(U,W)。n n定理定理2：可行流：可行流f是最大流的充是最大流的充分必要条件是：分必要条件是：f中不存在可改中不存在可改进路。进路。n n定理定理3：整流定理。：整流定理。如果网络中所有的弧的容量是如果网络中所有的弧的容量是整数，则存在整数值的最大流。整数，则存在整数值的最大流。n n定理定理4：最大流最小割定理。：最大流最小割定理。最大流等于最小割，即最大流等于最小割，即max V(f)=min C(U,W)。第9页/共52页最大流算法最大流算法n n第第1 1步，令步，令x=(xx=(xij ij)是任意整数可行流，可能是零流，给是任意整数可行流，可能是零流，给s s一个一个永久标号永久标号(-,)(-,)。n n第第2 2步步(找增广路找增广路)，如果所有标号都已经被检查，转到第，如果所有标号都已经被检查，转到第4 4步。步。找到一个标号但未检查的点找到一个标号但未检查的点i i,并做如下检查，并做如下检查，n n对每一个弧对每一个弧(i,j),(i,j),如果如果x xij ijC0,0,且且j j未标号，则给未标号，则给j j一个标号一个标号(-i,(j),(-i,(j),其中，其中，(j)=min(j)=minxxji ji,(i),(i)n n第第3 3步步(增广增广)，由点，由点t t开始，使用指示标号构造一个增广路开始，使用指示标号构造一个增广路,指指示标号的正负则表示通过增加还是减少弧流量来增加还是示标号的正负则表示通过增加还是减少弧流量来增加还是减少弧流量来增大流量，抹去减少弧流量来增大流量，抹去s s点以外的所有标号，转第二点以外的所有标号，转第二步继续找增广轨。步继续找增广轨。n n第第4 4步步(构造最小割构造最小割)，这时现行流是最大的，若把所有标号，这时现行流是最大的，若把所有标号的集合记为的集合记为S S，所有未标号点的集合记为，所有未标号点的集合记为T,T,便得到最小割便得到最小割(S,T)(S,T)。第10页/共52页实例实例第11页/共52页复杂度分析复杂度分析n n设图中弧数为m,每找一条增广轨最多需要进行2m次弧的检查。如果所有弧的容量为整数，则最多需要v(其中v为最大流)次增广，因此总的计算量为O(mv)。第12页/共52页procedure maxflow;最大流最大流var i,j,delta,x:integer;last:tline;可改进路中的前趋可改进路中的前趋 check:array0.maxn of boolean;检查数组检查数组begin repeat fillchar(last,sizeof(last),0);fillchar(check,sizeof(check),false);last1:=maxint;repeat i:=0;repeat inc(i)until(i n)or(lasti 0)and not checki;找到一个已检查而未标号的点找到一个已检查而未标号的点 if i n then break;for j:=1 to n do if lastj=0 then if flowi,j 0 then lastj:=-i;反向弧反向弧 checki:=true;until lastn 0;if lastn=0 then break;delta:=maxint;i:=n;repeat j:=i;i:=abs(lastj);if lastj 0 then x:=limiti,j-flowi,j else x:=flowj,i;if x 0 then inc(flowi,j,delta)else dec(flowj,i,delta);until i=1;放大网络流放大网络流 until false;end;第13页/共52页利用找增广路的其他流量算法利用找增广路的其他流量算法n n增广路的思想在于每次从源点搜索出一条前往汇点的增广路，并改变路上的边权，直到无法再进行增广：n n一般增广路方法：在剩余图中，一般增广路方法：在剩余图中，每次每次任意任意找一条增广路径增广。找一条增广路径增广。O(nmU)O(nmU)n n容量缩放增广路方法容量缩放增广路方法:在剩余图中，在剩余图中，每次任意找一条每次任意找一条最大可增广容量最大可增广容量和和的增广路径增广。的增广路径增广。O(nm*logU)O(nm*logU)n n最短增广路方法最短增广路方法(MPLA)(MPLA)：在剩余：在剩余图中，每次任意找一条图中，每次任意找一条含结点数含结点数最少最少的增广路径增广。的增广路径增广。O(nmO(nm2 2)n n连续最短增广路方法（连续最短增广路方法（DINICDINIC）：）：在剩余图中，每次在剩余图中，每次BFSBFS找增广路找增广路径增广路径时，记录每个点的距径增广路径时，记录每个点的距离标号。在距离标号最短路图上，离标号。在距离标号最短路图上，不断不断dfsdfs找增广路，找增广路，即一次标号，即一次标号，多次增广多次增广。O(nO(n2 2m)m)第14页/共52页DINICDINIC算法演示：算法演示：算法演示：算法演示：源点汇点422532汇点32对增广路进行增广，增广后退回到源点1汇点232汇点1找到增广路路线，（红色路线）找到增广路路线，（红色路线）对增广路进行增广，增广后退回到源点，再无增广路线3第15页/共52页用预流推进办法求网络流用预流推进办法求网络流n n预流推进算法给每一个顶点一个标号h(v)，表示该点到t的最短路（在残量网络中）。n n第一步hights()过程，就是BFS出初始最短路，计算出每一个顶点的h(v)。n n预流推进算法的特征是运用了预流来加快运算。预流说明图中的节点(除s,t)，仅需要满足流入量=流出量。其中流入量流出量的结点，我们称之为活动节点。我们的算法就是不断地将活动结点，变为非活动结点，使得预流成为可行流。第16页/共52页预流推进算法流程预流推进算法流程 算法过程算法过程prepare()prepare()，即首先将与，即首先将与s s相连的边设为满流，并将这时产相连的边设为满流，并将这时产生的活动结点加入队列生的活动结点加入队列QQ。这是算法的开始。这是算法的开始。以后便重复以下过程直到以后便重复以下过程直到QQ为空：为空：(1).(1).选出选出QQ的一个活动顶点的一个活动顶点u u。并依次判断残量网络。并依次判断残量网络GG中每条边中每条边(u,(u,v)v)，若，若h(u)=h(v)+1h(u)=h(v)+1，则顺着这里条边推流，直到，则顺着这里条边推流，直到QQ变成非活动变成非活动结点（不存在多余流量）。结点（不存在多余流量）。(Push(Push推流过程推流过程)(2).(2).如果如果u u还是活动结点。则需要对还是活动结点。则需要对u u进行重新标号：进行重新标号：h(u)=h(u)=minh(v)+1minh(v)+1，其中边，其中边(u,v)(u,v)存在于存在于G G 中。然后再将中。然后再将u u加入队列。加入队列。(relable(relable过程过程)可以证明，通过以上算法得到的结果就是最大流。可以证明，通过以上算法得到的结果就是最大流。第17页/共52页预流推进算法示例预流推进算法示例n n顶点u的通过量g(u)：n n剩余图中，找入边权和与出边权和的较小值l l增广时，每次找一个通过量最小的点v，从点vn n向源点“推”大小为g(v)的流量n n向汇点“拉”大小为g(v)的流量n n尽量使剩余图中的边饱和34578g(u)=12第18页/共52页用预流推进方法的一些网络流算用预流推进方法的一些网络流算法法n n预流推进的算法核心思想是以边为单元进行推流操作：n n一般的预流推进算法：在剩余图中，一般的预流推进算法：在剩余图中，维护一个预流维护一个预流，不断对活跃点执行，不断对活跃点执行pushpush操作，或者操作，或者relablerelable操作来重新操作来重新调整这个预流，直到不能操作。调整这个预流，直到不能操作。O(nmO(nm2 2)n n先进先出预流推进算法：在剩余图先进先出预流推进算法：在剩余图中，中，以先进先出队列维护活跃点以先进先出队列维护活跃点。O O(n(n3 3)n n最高标号预流推进算法：在剩余图最高标号预流推进算法：在剩余图中，中，每次检查最高标号的活跃点每次检查最高标号的活跃点，需要用到优先队列。需要用到优先队列。O(n O(n2 2mm1/21/2)第19页/共52页费用流费用流n n流最重要的应用是尽可能多的分流流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然了选择的余地，费用的因素就自然参与到决策中来。参与到决策中来。n n右图是一个最简单的例子：弧上标右图是一个最简单的例子：弧上标的两个数字第一个是容量，第二个的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的是费用。这里的费用是单位流量的花费，譬如花费，譬如fs1=4fs1=4，所需花费为，所需花费为3*4=123*4=12。n n容易看出，此图的最大流（流量是容易看出，此图的最大流（流量是8 8）为：）为：f fs1s1=f=f1t1t=5,f=5,fs2 s2=f=f2t2t=3=3。所。所以它的费用是：以它的费用是：3*5+4*5+7*3+2*3 3*5+4*5+7*3+2*3=62=62。(6,3)(5,4)(3,7)(8,2)STV1V2费用流问题第20页/共52页费用流定义费用流定义n n设有带费用的网络流图G=(V,E,C,W)，每条弧对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足：1.1.流量流量V(f)V(f)最大。最大。2.2.满足满足a a的前提下，流的费用的前提下，流的费用Cost(f)Cost(f)=E E(f(fij ij*W*Wij ij)最小。最小。就称f是网络流图G的最小费用最大流。n n最小费用可改进路最小费用可改进路设P是流f的可改进路，定义P+Wij-P-Wij 为P的费用(为什么如此定义？)如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可最小费用可改进路改进路。第21页/共52页费用流算法费用流算法n n求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。n n算法可描述为：n n第第1 1步步.令令f f为零流。为零流。n n第第2 2步步.若无最小费用可改进路，若无最小费用可改进路，转第转第5 5步；否则找到最小费用可改步；否则找到最小费用可改进路，设为进路，设为P P。n n第第3 3步步.根据根据P P求求deltadelta（改进量）。（改进量）。n n第第4 4步步.放大放大f f。转第。转第2 2步。步。n n第第5 5步步.算法结束。此时的算法结束。此时的f f即最小即最小费用最大流。费用最大流。第22页/共52页如何求最小费用可改进路如何求最小费用可改进路 n n设带费用的网络流图设带费用的网络流图G=(V,E,C,W)G=(V,E,C,W)，它的一个可行流是，它的一个可行流是f f。我们构造带权有向图。我们构造带权有向图B=(V,E)B=(V,E)，其中：，其中：n nV=VV=V。n n若若E E，f fij ijCCij ij，那么，那么EE，权为，权为WWij ij。若若E E，fij0fij0，那么，那么EE，权为，权为-W-Wij ij。n n显然，显然，B B中从中从S S到到T T的每一条道路都对应关于的每一条道路都对应关于f f的一条的一条可改进路；反之，关于可改进路；反之，关于f f的每条可改进路也能对应的每条可改进路也能对应B B中中从从S S到到T T的一条路径。即两者存在一一映射的逻辑关的一条路径。即两者存在一一映射的逻辑关系。系。n n故若故若B B中不存在从中不存在从S S到到T T的路径，则的路径，则f f必然没有可改进路；必然没有可改进路；不然，不然，B B中从中从S S到到T T的最短路径即为的最短路径即为f f的最小费用可改进路。的最小费用可改进路。n n现在的问题变成：给定带权有向图现在的问题变成：给定带权有向图B=(V,E)B=(V,E)，求从，求从S S到到T T的一条最短路径。的一条最短路径。第23页/共52页迭代法求最短路经迭代法求最短路经n n考虑到图中存在权值为负数的弧，不能采用考虑到图中存在权值为负数的弧，不能采用DijkstraDijkstra算法；算法；FloydFloyd算法的效率又不尽如人意算法的效率又不尽如人意所以，这里采用一种折衷的算法：所以，这里采用一种折衷的算法：迭代法（迭代法（bellmanbellman算法）。算法）。n n设设ShortiShorti表示从表示从S S到到i i顶点的最短路径长度；从顶点的最短路径长度；从S S到顶点到顶点i i的最短路的最短路径中，顶点径中，顶点i i的前趋记为的前趋记为LastiLasti。那么迭代算法描述如下：（为。那么迭代算法描述如下：（为了便于描述，令了便于描述，令n=|V|n=|V|，S S的编号为的编号为0 0，T T的编号为的编号为n+1n+1）n nstep 1.step 1.令令Shorti Shorti +（1in+11in+1），），Short0 Short0 0 0。n nstep 2.step 2.遍历每一条弧遍历每一条弧。若。若Shorti+ShortjShorti+Shortj，则，则令令Shortj Shortj Shorti+Shorti+，同时，同时Lastj Lastj i i。重复做。重复做step 2step 2直到直到不存在任何任何弧满足此条件为止。不存在任何任何弧满足此条件为止。n nstep 3.step 3.算法结束。若算法结束。若Shortn+1=+Shortn+1=+，则不存在从，则不存在从S S到到T T的路径；的路径；否则可以根据否则可以根据LastLast记录的有关信息得到最短路径。记录的有关信息得到最短路径。n n一次迭代算法的时间复杂度为一次迭代算法的时间复杂度为O(knO(kn2 2)，其中，其中k k是一个不大于是一个不大于n n的的变量。在费用流的求解过程中，变量。在费用流的求解过程中，k k大部分情况下都远小于大部分情况下都远小于n n。第24页/共52页procedure costflow;求最小费用最大流求最小费用最大流var i,j,x,delta:integer;best,last:tline;best：最短路长度；：最短路长度；last：可改进路中的前趋顶点：可改进路中的前趋顶点 more:boolean;begin repeat fillword(best,sizeof(best)shr 1,maxint);fillchar(last,sizeof(last),0);last1:=maxint;best1:=0;赋初值赋初值 repeat more:=false;for i:=1 to n do if besti maxint then for j:=1 to n do begin if(flowi,j limiti,j)and (besti+costi,j 0)and (besti-costj,i 0 then x:=limiti,j-flowi,j else x:=flowj,i;if x 0 then inc(flowi,j,delta)else dec(flowj,i,delta);until i=1;until false;根据改进量放大流根据改进量放大流end;第25页/共52页思维发散与探索思维发散与探索 n n可改进路费用：“递增！递增？”设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1p2p3pk呢？n n迭代法：“小心死循环！嘿嘿”迭代法会出现死循环吗？也就是说，构造的带权有向图B中会存在负回路吗？n n费用：“你在乎我是负数吗？”n n容量：“我管的可不仅是弧。”网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制：即通过此顶点的流量的上限；任务仍然是求从S到T的最小费用最大流。你能解决吗？第26页/共52页有上下界的最大流有上下界的最大流 n n上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧加上一个下界限制Aij(即必须满足Aijfij)。n n弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了。(3,0)(3,0)(3,0)(3,0)(10,1)原问题原问题33330(a)32231(b)增广增广第27页/共52页怎样找可行流怎样找可行流n n一种自然的想法是去掉下界，将其转化为只含上界的网络流图。一种自然的想法是去掉下界，将其转化为只含上界的网络流图。这种美好的愿望是可以实现的。具体方法如下：这种美好的愿望是可以实现的。具体方法如下：n n设原网络流图为设原网络流图为G=(V,E,C,A)G=(V,E,C,A)，构造不含下界的网络流图，构造不含下界的网络流图G=G=(V,E,C)(V,E,C)：1.1.V=VV=VS,TS,T2.2.对每个顶点对每个顶点x x，令，令h h-(x)=(x)=E E A AiX iX，若，若h h-(x)0(x)0，就添加一条，就添加一条弧弧，其上界为，其上界为h h-(x)(x)。3.3.对每个顶点对每个顶点x x，令，令h h+(x)=(x)=E E A AXi Xi，若，若h h+(x)0(x)0，就添加一条，就添加一条弧弧，其上界为，其上界为h h+(x)(x)。4.4.对于任何对于任何E E，都有，都有EE，其上界，其上界CCij ij=C=Cij ij A Aij ij。5.5.新增新增EE，其上界，其上界C CTSTS=+=+。6.6.在在GG中以中以S S为源点、为源点、TT为汇点求得最大流为汇点求得最大流f f。若。若f f中从中从S S发出的发出的任意一条弧是非饱和弧，则原网络流图没有可行流。否则可得任意一条弧是非饱和弧，则原网络流图没有可行流。否则可得原图的一个可行流原图的一个可行流f=f+Af=f+A，即所有的，即所有的f fij ij=f =f ij ij+A+Aij ij。7.7.然后再求可改进路（反向弧然后再求可改进路（反向弧必须满足必须满足f fij ijAAij ij，而非，而非f fij ij00），不断放大），不断放大f f，直到求出最大流。，直到求出最大流。第28页/共52页另外一种构图方法另外一种构图方法n nC(u,v)=C(u,v)-B(u,v)n n设n n如果如果MM(i i)非负，那么设一附加源非负，那么设一附加源S S0 0，则可以令，则可以令CC(S S0 0,i i)=)=MM(i i)。n n如果如果MM(i i)非负，那么设一附加汇非负，那么设一附加汇T T0 0，则可以令，则可以令CC(S S0 0,i i)=-)=-MM(i i)。n n在这样一个加入附加源和附加汇的流网络C中，如果任意g(S0,i)或g(i,T0)都达到满载，那么C中的这一个可行流g一定对应原网络G中的一个可行流f；反之G中的任意一个可行流f都可以对应C中的一个g(S0,i)或g(i,T0)都满载的流。第29页/共52页思考？思考？n n在一个容量有上下界的流网络G中，怎样尽快求源点s到汇点t的一个可行的最大流？n n在一个容量有上下界的流网络G中，怎样尽快求源点s到汇点t的一个可行的最小流？第30页/共52页多源点、多汇点的最大流多源点、多汇点的最大流n n已知网络流图有n个源点S1、S2、Sn，m个汇点T1、T2、Tm，求该图的最大流。这样的问题称为多源点、多汇点最大流。n n它的解决很简单：n n增设一个“超级源”S，对每个源点Si，新增弧，容量为无穷大。n n增设一个“超级汇”T，对每个汇点Ti，新增弧，容量为无穷大。n n以S为源点、T为汇点求最大流f。n n将f中的S和T去掉，即为原图的最大流。第31页/共52页顶点有容量限制的最大流顶点有容量限制的最大流n n对除源点和汇点之外的每个顶点对除源点和汇点之外的每个顶点i i拆分成两个顶拆分成两个顶点点i i和和i i。新增一条弧。新增一条弧，其容量为点，其容量为点i i的流的流量限制。量限制。n n对于原图中的弧对于原图中的弧，我们将其变换成，我们将其变换成。n n对变换后的图求最大流即可。对变换后的图求最大流即可。n n这里我们运用到了化归的思想：将未知的这里我们运用到了化归的思想：将未知的“点点限制限制”问题转化为已知的问题转化为已知的“边限制边限制”问题。问题。第32页/共52页网络流与二部图的匹配网络流与二部图的匹配n n设二部图为G=(X,Y,E)。n n增设点S，对于所有iX，新增弧，容量为1；增设点T，对于所有iY，新增一条弧，容量也为1。原图中所有的弧予以保留，容量均为+。对新构造出来的网络流图以S为源点、T为汇点求最大流：流量即为最大匹配数；若弧（iX，jY）的流量非零，它就是一条匹配边。n n二部图最大匹配问题解决。n n那么二部图的最佳匹配问题又如何？n n仍然按照上述方法构图。同时令原图中弧的费用保持不变；新增弧的费用置为0。然后以S为源点、T为汇点求最小费用最大流即可。最大流的费用即为原二部图最佳匹配的费用。第33页/共52页思考题思考题1：餐巾问题：餐巾问题n n某软件公司正在规划一项某软件公司正在规划一项n n天的软件开发计划，根据开发计划第天的软件开发计划，根据开发计划第i i天需天需要要ni ni个软件开发人员，为了提高工作效率，公司给软件人员提供了很个软件开发人员，为了提高工作效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有巾，这种毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，两种，A A种方式的消毒时间需要种方式的消毒时间需要a a天时间，天时间，B B中方式的消毒需要中方式的消毒需要b b天时间天时间（baba），），A A种消毒方式的费用为每块毛巾种消毒方式的费用为每块毛巾fAfA，B B种消毒方式的费用为种消毒方式的费用为每块毛巾每块毛巾fBfB，而买一块新毛巾的费用为，而买一块新毛巾的费用为f f（新毛巾是已消毒的，当天可（新毛巾是已消毒的，当天可以使用）；而且以使用）；而且ffAfBffAfB。公司经理正在规划在这。公司经理正在规划在这n n天中，每天买多少天中，每天买多少块新毛巾、每天送多少块毛巾进行块新毛巾、每天送多少块毛巾进行A A种消毒和每天送多少块毛巾进行种消毒和每天送多少块毛巾进行B B种消毒。当然，公司经理希望费用最低。种消毒。当然，公司经理希望费用最低。你的任务就是：求出提供毛巾服务的最低总费用。你的任务就是：求出提供毛巾服务的最低总费用。n n输入文件：第输入文件：第1 1行为行为n,a,b,f,fA,fB.n,a,b,f,fA,fB.第第2 2行为行为n n1 1,n,n2 2,n,nn n（注：（注：1f,fA,fB60,1n10001f,fA,fB60,1n1000）n n输出文件：最少费用输出文件：最少费用input.txt output.txtinput.txt output.txt4 1 2 3 2 1 384 1 2 3 2 1 38 8 2 1 6 8 2 1 6第34页/共52页分析分析n n公司第公司第i i天需要天需要n ni i 块毛巾，可以把这块毛巾，可以把这n ni i 块毛巾的来源列举如下：块毛巾的来源列举如下：新买的毛巾。新买的毛巾。第第i a 1i a 1天之前通过天之前通过A A种方式消毒的毛巾。种方式消毒的毛巾。第第i b 1i b 1天之前通过天之前通过B B种方式消毒的毛巾。种方式消毒的毛巾。n n我们构造带费用的网络流图我们构造带费用的网络流图G=(V,E,C)G=(V,E,C)。V=S,VV=S,V1 1,V,V2 2,V,Vn n,V,V1 1,V,V2 2,V Vn n,T,T，其中，其中S S是源点、是源点、T T是汇点。是汇点。E E中包含如下几类弧：中包含如下几类弧：1.1.S,V（1in1in），容量为），容量为ni ni，费用为，费用为0 0。表示第。表示第i i天需要天需要n ni i块毛巾。块毛巾。2.2.V,T（1in1in），容量为正无穷大，费用为），容量为正无穷大，费用为f f。该弧的流量表示第。该弧的流量表示第i i天天通过方式通过方式a a得到的毛巾数量。得到的毛巾数量。3.3.V（a+2ina+2in），容量为正无穷大，费用为），容量为正无穷大，费用为fAfA。该弧的流量表。该弧的流量表示第示第i i天通过方式天通过方式b b得到的毛巾数量。得到的毛巾数量。4.4.V（b+2inb+2in），容量为正无穷大，费用为），容量为正无穷大，费用为fBfB。该弧的流量表。该弧的流量表示第示第i i天通过方式天通过方式c c得到的毛巾数量。得到的毛巾数量。5.5.V（2in2in），容量为正无穷大，费用为），容量为正无穷大，费用为0 0。由于题目中没有说。由于题目中没有说消毒完的毛巾要马上使用，所以第消毒完的毛巾要马上使用，所以第3 3天就消毒好的毛巾可以暂且留着，天就消毒好的毛巾可以暂且留着，到第到第7 7天、第天、第8 8天再使用也可以。因此这里增设此弧。天再使用也可以。因此这里增设此弧。6.6.V,T（1in1in），容量为），容量为n ni i，费用为，费用为0 0。n n然后对这个网络流图以然后对这个网络流图以S S为源点、为源点、T T为汇点的求最小费用最大流即可。求得为汇点的求最小费用最大流即可。求得的最大流费用就是原问题的答案。的最大流费用就是原问题的答案。第35页/共52页思考题思考题2：Agentn n有有有有n n名双重间谍潜伏在敌军内部，分别编号为名双重间谍潜伏在敌军内部，分别编号为名双重间谍潜伏在敌军内部，分别编号为名双重间谍潜伏在敌军内部，分别编号为1,2,3,n1,2,3,n。在给定的时间内，任意两人之间至多只进行一次点对点的在给定的时间内，任意两人之间至多只进行一次点对点的在给定的时间内，任意两人之间至多只进行一次点对点的在给定的时间内，任意两人之间至多只进行一次点对点的双人联系。双人联系。双人联系。双人联系。n n数据将给你一份表格，表格中将提供任意两位间谍数据将给你一份表格，表格中将提供任意两位间谍数据将给你一份表格，表格中将提供任意两位间谍数据将给你一份表格，表格中将提供任意两位间谍i i和和和和j j之间之间之间之间进行联系的安全程度，用一个进行联系的安全程度，用一个进行联系的安全程度，用一个进行联系的安全程度，用一个00，11的实数的实数的实数的实数SijSij表示；以及表示；以及表示；以及表示；以及他们联系时，能够互相传递的消息的最大数目，用一个正他们联系时，能够互相传递的消息的最大数目，用一个正他们联系时，能够互相传递的消息的最大数目，用一个正他们联系时，能够互相传递的消息的最大数目，用一个正整数表示整数表示整数表示整数表示MijMij。（如果在表格中没有被提及，那么间谍。（如果在表格中没有被提及，那么间谍。（如果在表格中没有被提及，那么间谍。（如果在表格中没有被提及，那么间谍i i和和和和j j之间不进行直接联系）。之间不进行直接联系）。之间不进行直接联系）。之间不进行直接联系）。n n假消息从盟军总部传递到每个间谍手里的渠道也不是绝对假消息从盟军总部传递到每个间谍手里的渠道也不是绝对假消息从盟军总部传递到每个间谍手里的渠道也不是绝对假消息从盟军总部传递到每个间谍手里的渠道也不是绝对安全的，我们用安全的，我们用安全的，我们用安全的，我们用00，11的实数的实数的实数的实数ASjASj表示总部与间谍表示总部与间谍表示总部与间谍表示总部与间谍j j之间进行之间进行之间进行之间进行联系的安全程度，联系的安全程度，联系的安全程度，联系的安全程度，AMjAMj则表示总部和间谍则表示总部和间谍则表示总部和间谍则表示总部和间谍j j之间进行联系时之间进行联系时之间进行联系时之间进行联系时传递的消息的最大数目。对于不和总部直接联系的间谍，传递的消息的最大数目。对于不和总部直接联系的间谍，传递的消息的最大数目。对于不和总部直接联系的间谍，传递的消息的最大数目。对于不和总部直接联系的间谍，他的他的他的他的AMj=0AMj=0（而表格中给出的他的（而表格中给出的他的（而表格中给出的他的（而表格中给出的他的ASjASj是没有意义的）。是没有意义的）。是没有意义的）。是没有意义的）。第36页/共52页n n当然，假消息从间谍手中交到敌军的情报部官员的办公桌上的当然，假消息从间谍手中交到敌军的情报部官员的办公桌上的当然，假消息从间谍手中交到敌军的情报部官员的办公桌上的当然，假消息从间谍手中交到敌军的情报部官员的办公桌上的过程是绝对安全的，也就是说，间谍与敌军情报部门之间要么过程是绝对安全的，也就是说，间谍与敌军情报部门之间要么过程是绝对安全的，也就是说，间谍与敌军情报部门之间要么过程是绝对安全的，也就是说，间谍与敌军情报部门之间要么不进行联系，要么其联系的安全程度是不进行联系，要么其联系的安全程度是不进行联系，要么其联系的安全程度是不进行联系，要么其联系的安全程度是1 1（即完全可靠）。（即完全可靠）。（即完全可靠）。（即完全可靠）。n n现在我军司令部想利用这些间谍将现在我军司令部想利用这些间谍将现在我军司令部想利用这些间谍将现在我军司令部想利用这些间谍将k k条假消息发布到敌军情报机条假消息发布到敌军情报机条假消息发布到敌军情报机条假消息发布到敌军情报机关的负责人。消息先由总部一次性发给关的负责人。消息先由总部一次性发给关的负责人。消息先由总部一次性发给关的负责人。消息先由总部一次性发给n n名间谍中的一些人，再名间谍中的一些人，再名间谍中的一些人，再名间谍中的一些人，再通过它们之间的情报网传播，最终由这通过它们之间的情报网传播，最终由这通过它们之间的情报网传播，最终由这通过它们之间的情报网传播，最终由这n n名间谍中某些人将情报名间谍中某些人将情报名间谍中某些人将情报名间谍中某些人将情报送到敌军手中。送到敌军手中。送到敌军手中。送到敌军