网络流与匹配最大的

一、F。这个流称为满足供需约束的可行流。

F(e)

F(e)

F F

AXi

F(e) F(e)P(Yj ［问题求解新增两个顶点x0,y0。加m条以x0为尾的边（x0,x1）,(x0,x2),…,(x0,xm)每边的容量c(x0,xi)=A(xi)nx0为源点，y0nn

F 将下界“分离”0D的每一B(e)D改造为“每条边仅对应一个容量”的D’B(e)。D

S1S12T第一步：分离必要弧（红线为必要弧S12T S12T （x,yi---x---y---j其中弧（i,x）,(y,j)的容量为B(e)，弧（x,y）的容量为∞。S12T33S12T332233XY（x,yDD’构造成功。414414SS12T332233XYD’y到汇x2+3+3，则必要弧都饱和。D’F使得所有与源（或汇）相连的弧都饱和。DD’f1f1满足等于所有边容量下界之和D

，则f1Ff1可增大，在寻找增广路（u,t’（s’,uDD’C(e)-B(e)（t,sD1的最大流ff=

DD2D2fD的最大流。D1s’,t’f1f1（e（D2上的流量不平衡D2中的增广路径D设st[x]为以顶点x为尾的边容量下界之和，ed[y]以y为头的边容量下界之和，tflow为dinic算法。 Fori:=vstovtdofirst[i]:=-1;Fori:=1tomdo {读入第i条边（x,y，容量下界bb，上界cc} {计算以x为尾的边容量下界和，以y为头的边容量下 {求容量下界和 （x,y{对原网络D的每一个顶点添加容量 的新边（i,vt），添加容量B(e)的新边Fori:=1tondobeginadd(I,vt,st[i]);add(vs,I,ed[i]);end; dinicif {f1≠

则无解 fori:=1tondoforj:=1to2do 再次用dinic算法扩增残留网D2的流，得到最大流tempAns:=temp+st[1];{再加上流出源点流量下界之和，得原网络的最大流} （一）示每吨物资通过该公路的费用（单价。现在的问题是怎样安排，才能使得从起点到终量费用Bij≥0。上述问题的求解目标是：求一个最大流，使总的费用

Bij*(vi,vj（二）我们首先一下，当沿着一条关于可行流F的可增广路P，以δ=1调整F，得到新的可行F’V(F’)=V(F)+1B(F’)B(F)增加了多少？B(F’)-B(F)=[Bij*(F'ijFij)

Bij*(F'ijFij)B(F’)-B(F)=Bij

Bijp我们把Bij

称为这条可增广路Ｐ的“费用” V(F)的所有可行流中费用最小者，而Ｐ是关于Ｆ的所有可增广路中费Bij≥F=0F=0开始。U(F)的最小费用流。余下的问题是如何去寻找关于该流Ｆ的最小（Vj,iWij为：Vt的最短路。1)W(F(k-1))W(F(k-1))VsVt的最短路。+∞DPPF(k-1)进行改进F(k)F(k)重复上述步骤。1 {弧类型 {容量 Settype=setofN1,Node:array[1..maxn]ofinteger; Arc:array[1..maxn,1..maxn]ofarctype; W,b:array[1..maxn,1..maxn]ofinteger; 2<1>startendsmin=maxint。Proceduregetting_path(s,tot:integer;m:settype){s为待扩展结点，tot当前路径代价，m当前最佳路径结点集合}Vari:integer;Ifs=endsthenIftot<minthenElseFori:=1ton (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;Functionford(vara:integer):boolean;VarI,j,m,s:integer;Fori:=1tondo {W图初始化}Forj:=1tondow[I,j]:=maxint;Fori:=1tondo {W图赋权}Forj:=1tondoWitharc[I,j]doIfmax>0thenIfact<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} Ifmin=maxintthen Beginford:=true;exitend;M:=ends;a:=maxint; Ifnode[j]<0thenIfnode[j]>0thens:=arc[m,j].max-arc[m,j].act;Ifs<athena:=s;Untilm=start;End;{ford}Procedurefulkerson(a:integer);VarI,m,j:integer;Ifnode[j]<0th