最大流算法

图论算法---最大流问题长沙市雅礼中学朱全民运输网络现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？4248473621STV1V2V3V4公路运输图基本概念这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。若有向图G=(V,E)满足下列条件：1.有且仅有一个顶点S，它的入度为零，即d-(S)=0，这个顶点S便称为源点，或称为发点。2.有且仅有一个顶点T，它的出度为零，即d+(T)=0，这个顶点T便称为汇点，或称为收点。3.每一条弧都有非负数，叫做该边的容量。边(vi,vj)的容量用cij表示。则称之为网络流图，记为G=(V,E,C)可行流可行流对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。1.每一条弧(i,j)有fij≤Cij2.流量平衡除源点S和汇点T以外的所有的点vi，恒有：∑j(fij)=∑k(fjk)该等式说明中间点vi的流量守恒，输入与输出量相等。3.对于源点S和汇点T有，∑i(fSi)=∑j(fjT)=V(f)可改进路给定一个可行流f={fij}。若fij=Cij，称vi,vj为饱和弧；否则称vi,vj为非饱和弧。若fij=0，称vi,vj为零流弧；否则称vi,vj为非零流弧。定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。譬如在图中，P=(S,V1,V2,V3,V4,T)，那么P+={S,V1,V1,V2,V2,V3,V4,T}P-={V4,V3}给定一个可行流f，P是从S到T的一条道路，如果满足：fij是非饱和流，并且i,j∈P+,fij是非零流，并且i,j∈P-那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。割切G=(V,E,C)是已知的网络流图，设U是V的一个子集，W=V\U，满足SU，TW。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：上例中，令U={S,V1}，则W={V2,V3,V4,T}，那么C(U,W)=S,V2+V1,V2+V1,V3+V1,V4=8+4+4+1=17WjUiijcWUC),(割切上例中，令U={S,V1}，则W={V2,V3,V4,T}，那么，C(U,W)=S,V2+V1,V2+V1,V3+V1,V4=8+4+4+1=17流量算法的基本理论定理1：对于已知的网络流图，设任意一可行流为f，任意一割切为(U,W)，必有：V(f)≤C(U,W)。定理2：可行流f是最大流的充分必要条件是：f中不存在可改进路。定理3：整流定理。如果网络中所有的弧的容量是整数，则存在整数值的最大流。定理4：最大流最小割定理。最大流等于最小割，即maxV(f)=minC(U,W)。最大流算法第1步，令x=(xij)是任意整数可行流，可能是零流，给s一个永久标号(-,∞)。第2步(找增广轨)，如果所有标号都已经被检查，转到第4步。找到一个标号但未检查的点i,并做如下检查，对每一个弧(i,j),如果xijCij,且j未标号,则给j一个标号(+i,δ(j)),其中，δ(j)=min{Cij-xij,δ(i)}对每一个弧(j,i),如果xji0,且j未标号，则给j一个标号(-i,δ(j)),其中，δ(j)=min{xji,δ(i)}第三步(增广)，由点t开始，使用指示标号构造一个增广路,指示标号的正负则表示通过增加还是减少弧流量来增加还是减少弧流量来增大流量，抹去s点以外的所有标号，转第二步继续找增广轨。第四步(构造最小割)，这时现行流是最大的，若把所有标号的集合记为S，所有未标号点的集合记为T,便得到最小容量割(S,T)。实例复杂度分析设图中弧数为m,每找一条增广轨最多需要进行2m次弧的检查。如果所有弧的容量为整数，则最多需要v(其中v为最大流)次增广，因此总的计算量为O(mv)。proceduremaxflow;{最大流}vari,j,delta,x:integer;last:tline;{可改进路中的前趋}check:array[0..maxn]ofboolean;{检查数组}beginrepeatfillchar(last,sizeof(last),0);fillchar(check,sizeof(check),false);last[1]:=maxint;repeati:=0;repeatinc(i)until(in)or(last[i]0)andnotcheck[i];{找到一个已检查而未标号的点}ifinthenbreak;forj:=1tondoiflast[j]=0thenifflow[i,j]limit[i,j]thenlast[j]:=i{正向弧}elseifflow[j,i]0thenlast[j]:=-i;{反向弧}check[i]:=true;untillast[n]0;iflast[n]=0thenbreak;delta:=maxint;i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]0thenx:=limit[i,j]-flow[i,j]elsex:=flow[j,i];ifxdeltathendelta:=x;untili=1;{求改进量}i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);untili=1;{放大网络流}untilfalse;end;费用流流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。右图是一个最简单的例子：弧上标的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的花费，譬如fs1=4，所需花费为3*4=12。容易看出，此图的最大流（流量是8）为：fs1=f1t=5,fs2=f2t=3。所以它的费用是：3*5+4*5+7*3+2*3=62。(6,3)(5,4)(3,7)(8,2)STV1V2费用流问题费用流定义设有带费用的网络流图G=(V,E,C,W)，每条弧Vi,Vj对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足：1.流量V(f)最大。2.满足a的前提下，流的费用Cost(f)=∑i,j∈E(fij*Wij)最小。就称f是网络流图G的最小费用最大流。最小费用可改进路设P是流f的可改进路，定义∑vi,vj∈P+Wij-∑vi,vj∈P-Wij为P的费用(为什么如此定义？)如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。算法求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。算法可描述为：第1步.令f为零流。第2步.若无最小费用可改进路，转第5步；否则找到最小费用可改进路，设为P。第3步.根据P求delta（改进量）。第4步.放大f。转第2步。第5步.算法结束。此时的f即最小费用最大流。如何求最小费用可改进路设带费用的网络流图G=(V,E,C,W)，它的一个可行流是f。我们构造带权有向图B=(V’,E’)，其中：V’=V。若Vi,Vj∈E，fijCij，那么Vi,Vj∈E’，权为Wij。若Vi,Vj∈E，fij0，那么Vj,Vi∈E’，权为-Wij。显然，B中从S到T的每一条道路都对应关于f的一条可改进路；反之，关于f的每条可改进路也能对应B中从S到T的一条路径。即两者存在一一映射的逻辑关系。故若B中不存在从S到T的路径，则f必然没有可改进路；不然，B中从S到T的最短路径即为f的最小费用可改进路。现在的问题变成：给定带权有向图B=(V’,E’)，求从S到T的一条最短路径。迭代法求最短路经考虑到图中存在权值为负数的弧，不能采用Dijkstra算法；Floyd算法的效率又不尽如人意——所以，这里采用一种折衷的算法：迭代法。设Short[i]表示从S到i顶点的最短路径长度；从S到顶点i的最短路径中，顶点i的前趋记为Last[i]。那么迭代算法描述如下：（为了便于描述，令n=|V’|，S的编号为0，T的编号为n+1）step1.令Short[i]+∞（1≤i≤n+1），Short[0]0。step2.遍历每一条弧Vi,Vj。若Short[i]+i,jShort[j]，则令Short[j]Short[i]+i,j，同时Last[j]i。重复做step2直到不存在任何任何弧满足此条件为止。step3.算法结束。若Short[n+1]=+∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n。procedurecostflow;{求最小费用最大流}vari,j,x,delta:integer;best,last:tline;{best：最短路长度；last：可改进路中的前趋顶点}more:boolean;beginrepeatfillword(best,sizeof(best)shr1,maxint);fillchar(last,sizeof(last),0);last[1]:=maxint;best[1]:=0;{赋初值}repeatmore:=false;fori:=1tondoifbest[i]maxintthenforj:=1tondobeginif(flow[i,j]limit[i,j])and(best[i]+cost[i,j]best[j])thenbeginbest[j]:=best[i]+cost[i,j];last[j]:=i;more:=true;end;if(flow[j,i]0)and(best[i]-cost[j,i]best[j])thenbeginbest[j]:=best[i]-cost[j,i];last[j]:=-i;more:=true;end;end;untilnotmore;{找最优可改进路}ifbest[n]=maxintthenbreak;delta:=maxint;i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]0thenx:=limit[i,j]-flow[i,j]elsex:=flow[j,i];ifxdeltathendelta:=x;untili=1;{求改进量}i:=n;repeatj:=i;i:=abs(last[j]);iflast[j]0theninc(flow[i,j],delta)elsedec(flow[j,i],delta);untili=1;untilfalse;{根据改进量放大流}end;思维发散与探索可改进路费用：“递增！递增？”设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢？迭代法：“小心死循环！嘿嘿……”迭代法会出现死循环吗？也就是说，构造的带权有向图B中会存在负回路吗？费用：“