网络最大流的推广

网络最大流的推广一、 计算多源多汇的可行流下图是一个商品供应系统，边的方向表示商品流向，边上的数字表示商品从某地至某地的最大通过能力。商品的资源来自于xl,x2,x3,其中x1的供应量为5,x2为10,x3为5。这些商品在商场yl,y2,y3出售。yl的需求为5,y2为10,y3为5。问是否所有的需求可同时被满足？上述网络是一个特殊的网络。在这个网络中,源点和汇点都不止一个。对于每一个源点xi,存在一个供应量；对于每一个汇点yi,也存在一个需求量。题目所求的是所有汇点的需求量是否可同时被满足的问题。对于上述网络，每条边e对于一个边容量c(e),源点集合X={xl,x2,...,xm},A(xi)是源点xi的供应量，汇点集合y={yl,y2,...,yn},P(yj)是汇点yj的需求量。要求满足下列条件的流F。这个流称为满足供需约束的可行流。对于所有边e：。弐⑹*、对于所有中间点u：ee以为头的弧集ee以为尾的弧集对于产地X:i工F(e)- Xr(e)<A(X)iee以.为头的弧集ee以"为尾的弧集ii对于销地Yj：j^F(e)- ^F(e)>P(Y)jee以Y.为尾的弧集ee以Y.为头的弧集jj［问题求解］(1) 构造新网络D'新增两个顶点x0,y0。加m条以x0为尾的边(x0,x1),(x0,x2),...,(x0,xm)每边的容量

c(xO,xi)=A(xi)；同样加n条以y0为头的边(yl,yO),(y2,y0),...,(yn,yO)每边的容量c(yi,yO)=P(yi);以x0为源点，y0为汇点。(2)求D'的最大流，若F=丄P(Y) ，则F满足供需要求。ii=1二、求容量有上下界的网络的最大流网络中每条边e对应两个数字B(e)和C(e),分别表示边容量的下界和上界。那么如何求可行流和最大流呢？标准的网络是容量有上下界网络的一种特例，即B(e)=O。当B(e)>0时，网络不一定存在流。如下图如何判断容量有上下界网络存在可行流。将下界“分离”出去，从而使问题转为下界为0的情况，即将容量有上下界的网络D的每一条边分离成两条边。其中一条边的容量是C(e)-B(e)，另一条边的容量固定为B(e)。我们把容量固定为B(e)的边称为必要弧。经过这种分离，网络D改造为“每条边仅对应一个容量”的附加网D'。对D'进行求最大里，根据求解结果，判断D是否有可行流F,这一可行流F中，所有D'中的必要弧上流量必须等于弧的固定容量B(e)0构造对应的附加网D'首先分析最简单的情况：网络D仅含一条路径，如下图所示2,622,62第一步：分离必要弧(红线为必要弧)4 1—42 3 3第二步：改造。在上面等价图中增加一条边(x,y)，顶点i至顶点j的必要弧修正为其中弧(i,x),(y,j)的容量为B(e)，弧(x,y)的容量为改造后的网是一个无源汇的网络，无源汇网的可行流一定可使必要弧饱和。去除弧（x,y）,增加一条边t至s容量为+w的弧，使y为新的源，x为新的汇。至此，网络D的附加网络D'构造成功。网络D'网络D'的最大流F使得所有与源（或汇）相连的弧都饱和。3.求D的最大流，则f1求得附加网D'的最大流fl后，当fl满足等于所有边容量下界之和工B（e）为原网络D，则f1接着我们将弧（s,t）去除，添加的源汇去除，将D'恢复为经分边的等价网D1，在其可行流fl的基础再扩大流量，最终求得一个符合要求的最大流F。如果fl可增大，在寻找增广路径时要注意必要弧不能退流。为此，在回复后的D1中，先将必要弧展示拿走，即在剩余网络中将所有的必要弧展示拿走，形成一个新的附加网络D2,这个附加网络中，源汇仍然是s，t,边上的容量C（e）-B（e）,流量为fl（e），所有必要弧都删除。对D2的初始流fl进行流的扩展。由此得到计算容量有上下界的网络最大流的一般方法：（1） 新增两个顶点s'和t'，s'称附加源，t'称附加汇；（2） 对原网络D的每一个顶点u,加一条边（u,t'）,边的容量为原网中以u为尾的边容量下界之和；（3） 对原网络D的每一个顶点u,加一条边（s',u）,边的容量为原网中以u为头的边容量下界之和；（4） 原网络D的每一条边在D'仍保留，边容量修正为C（e）-B（e）；（5） 再添加一条新边（t,s）,边容量为+w；（6） 求附加网络Dl的最大流f,若f=工B（e） ，则D网有可行流f；

(7)将D1中的弧(t,s)去掉，所有的必要弧都删除，D1被恢复以s为源，t为汇的无容量下界网络D2。对D2的初始可行流f进行扩展，求D的最大流。例：下图为一个容量有上下界的网路D,边上的数第一个为B(e)，第二个为C(e)做附加网络D2，边上的流量为D1中流量做附加网络D2，边上的流量为D1中流量fl(e),如图所示边上标出的流量为剩余流量，其上面没有标出必要弧的流量，因此，可把网络D2看为D的残留网络。(可以看出，附加网络D2上的流量不平衡)在其上面的当前流为起始流，寻找增广路径，进行扩增流量。原网络D中的最大流为10红色为弧上的实际流量4.求容量有上下界的网络最大流算法设st[x]为以顶点x为尾的边容量下界之和，ed[y]存储以y为头的边容量下界之和，tflow为所有边容量下界之和。其他数据结构参考dinic算法。算法描述如下Readln(n,m); ｛读顶点数和边数｝Vs:=0;vt:=n+1; ｛设计附加源和附加汇｝Fori:=vstovtdofirst[i]:=-l;Tflow:=0;Fori:=ltomdo ｛依次读入每条边信息｝BeginReadln(x,y,bb,cc);｛读入第i条边(x,y),容量下界bb,上界cc｝St[x]:=st[x]+bb;ed[y]:=ed[y]+bb; ｛计算以x为尾的边容量下界和，以y为头的边容量下界之和｝Tflow:=tflow+bb;｛求容量下界和｝Add(x,y,cc-bb); ｛保留原第i条边(x,y),边容量修正为C(e)-B(e)｝End;｛对原网络D的每一个顶点添加容量为 工B(e) 的新边(i,vt)，添加容量为ew以i为尾的弧集乂B(e)的新边(vs,i)｝ew以i为头的弧集Fori:=ltondobeginadd(I,vt,st[i]);add(vs,I,ed[i]);end;Add(n,1,maxw); ｛再添加一条容量为的新边(t,s)｝采用dinic算法尖酸附加网的最大流tempiftempotflow ｛若附加网的最大流fl工丫B(e) 则无解｝then输出无解信息else ｛恢复原网络的源点、汇点和边指针，得到残留网络D2｝beginvs:=1;vt:=n;first[vs]:=g[first[vs]].next;first[vt]:=g[first[vt]].next;fori:=1tondoforj:=1to2do ｛附加网中每个顶点多出一条边，多出的一条边在读顶点的边链表中，又附加了一条反向边，所以要向后退两个位置｝beginfirst[i]:=g[first[i]].next;first[i]:=g[first[i]].next;end;再次用dinic算法扩增残留网D2的流，得到最大流tempAns:=temp+st[1];｛再加上流出源点流量下界之和，得原网络的最大流｝Writeln(ans); ｛输出最大流｝End;三、最小费用最大流问题(一)问题描述在实际问题中，设计“流”的同时，人们考虑的还不只是流量，而且还有“费用”的因素。例如下图是一个公路网，Vs是仓库甲所在地，即物资输送的起点，Vt为仓库乙，即物资的终点，每一条弧标有两个数字。第1个数字表示某一时间段里通过公路的最多吨数，第2个数字表示每吨物资通过该公路的费用(单价)。现在的问题是怎样安排运输，才能使得从起点到终点的物资最多，又使得总的运费最少？显然，这是一个网络流图，其每一条弧Vi,Vj)除给定的容量Cij外，还给定了一个单位流量费用Bij>0o上述问题的求解目标是：求一个最大流，使总的费用B(f)=工B*Fijij(vi,vj)wE取极小值(二)最小费用最大流算法1、根据最小费用的定义，求最小费用最大流的算法设计思路：我们首先考察一下，当沿着一条关于可行流F的可增广路P,以5=1调整F,得到新的可行流F',则源点的净输出量V(F')=V(F)+1。而B(F')比B(F)增加了多少？B(F')-B(F)=[工B*(F'-F)—ijijij工B*(F'-F)]ijijijp+p-Fij'-Fij=5=1B(F')-B(F)=工B-工Bijij我们把工B-工B 称为这条可增广路P的“费用”ijijp+ p-其次，若F是流量为V(F)的所有可行流中费用最小者，而P是关于F的所有可增广路中费用最小的可增广路，那么沿P去调整F,得到的可行流F',即流量为V(F')的所有新的可行流中的最小费用流。这样，当F是最大流时，它也是我们所要求的最小费用最大流了。2、由于Bij^O所以可行流F=0必是流量为0的最小费用流。这样，总可以以F=0开始。一般地，设已知F是流量U(F)的最小费用流。余下的问题是如何去寻找关于该流F的最小费用可增广路。为此，我们构造一个带权有向图W(F)，他的顶点时原网络D的顶点，而把D中的每一条弧(Vi,Vj)变成两个方向相反的弧(Vi,Vj)和(Vj,Vi)，定义W(F)中弧的权Wij为：于是在网络中寻求关于F的最小费用可增广路，就等价于在带权有向图W(F)中，寻求从Vs到Vt的最短路。因此有如下算法：开始时取可行流中最小费用流F=0，记为F(0)=0,—般地，若在第k-1步得到最小费用流F(k-l),则构造带权有向图W(F(k-l))，在W(F(k-l))中，寻求Vs到Vt的最短路。若不存在最短路(即最短路的权是+8),则F(k-l)即最小费用最大流；若存在最短路，则在原网络D中得此相应的可增广路P,在可增广路P上对F(k-1)进行改进得到新的最小费用可行流F(k)，再对F(k)重复上述步骤。下面以一开始提到的公路网为例：最小费用最大流算法实现1、数据结构Const maxn=＜顶点数〉TypeArctype=record ｛弧类型｝Max:integer; ｛容量｝Act:integer; ｛流量｝End;Settype=setofbyte;VarN1,Node:array[1..maxn]ofinteger; ｛辅助容量，最佳路径序列｝Arc:array[1..maxn,1..maxn]ofarctype; ｛网络｝W,b:array[1..maxn,1..maxn]ofinteger; ｛最小费用和单位费用｝Success:boolean;Start,ends,a,n,min:integer; ｛发点，收点，改变量，结点个数，最佳代价｝2、主要算法<1>求从start到ends的最短路径，若无最短路，则min=maxint。Proceduregetting_path(s,tot:integer;m:settype)｛s为待扩展结点，tot当前路径代价，m当前最佳路径结点集合｝Vari:integer;BeginIfs=endsthenBeginIftot<minthenBeginMin:=tot;node:=n1End;EndElsebeginFori:=1tondoIf(w(s,i)<>maxint)andnot(Iinm)ThenbeginIfarc[s,i].act<arc[s,i].maxthenn1[i]:=s;Ifarc[I,s].act>0thenn1[i]:=-s;Ifi=endsthenn1[i]:=s;Getting.path(I,tot+w[s,i],m+[i])End;End;End;<2>建图W,若存在最佳路径，根据该路径标号改进流Functionford(vara:integer):boolean;｛若无最佳路径，返回true，进行标号过程，返回false｝VarI,j,m,s:integer;BeginFord:=false;Fori:=1tondo｛W图初始化｝Forj:=1tondow[I,j]:=maxint;Fori:=1tondo｛根据当前可行流，给W图赋权｝Forj:=1tondoWitharc[I,j]doIfmax>0thenBeginIfact<maxthenw[I,j]:=b[I,j];Ifact=maxthenw[I,j]:=maxint;Ifact>0thenw[j,i]:=-b[I,j];Ifact=0thenw[j,i]:=maxint;End;｛with｝N1[start]:=start;｛初始结点进入增广路｝Min:=mxint; ｛最佳