10-最大流问题.

最大流问题•在一个单源单汇的简单有向图引入流量因素，且要求计算满足流量限制和平衡条件的最大可行流时，就产生了最大流问题。基本概念（1）网络的定义：设D是一个简单有向图D=(V,E)。在V中指定了一个源点（记为Vs）和一个汇点（记为Vt），对于每一条弧（Vi，Vj）∈E，对应有一个Cij=0，称为弧的容量。也记为D=（V，E，C）。（2）网络的可行流F。满足下述条件的流F称为网络的可行流。•流的容量限制：对于每条弧（u,v）∈E来说，弧流量为一个不大于弧容量的非负数，即0=f(u,v)=C(u,v)。•流的平衡条件：除源点和汇点外的任意中间点u，流入u的“流量”与流出u的“流量”相等。（3）网络的流量V(F)：指源点的净流出流量和汇点的净流入流量。寻找网络G上可能的最大流量即为网络G上的最大流问题在可增广路径的基础上计算最大流•最大流算法的核心是计算可增广路径可增广路径的基本概念•退流的概念和弧的分类•若p是网络中连接源点s和汇点t的一条路，且路的方向是从s到t的，则路上的弧有前向弧和后向弧两种。•前向弧：弧的方向与路的方向一致。前向弧的全体记为p+•后向弧：弧的方向与路的方向相反。后向弧的全体记为p-可增广路径的定义•设F是一个可行流，p是从s到t的一条路，若p满足下述两个条件，则称p是关于可行流F的一条可增广路径，亦称可改进路径：•在p+的所有前向弧（u,v）上，0=f(u,v)C(u,v)。•在p-的所有后向弧（u,v）上，0f(u,v)=C(u,v)。增广路径SACBDET在可增广路径p上改进流量•残留网络•按照上述方法对弧进行分类，初始流图中的每条弧既有容量又有前向弧流量和后向弧流量，因此不够简洁，不方便寻找可增广路径。•所谓残留网络，就是将初始流图上的前向弧的容量调整为“剩余容量”=C(u,v)-f(u,v)；后向弧的容量调整为“可退流量”=f(v,u)；去除“剩余流量”为0的弧。在这样的图上找可增广路经变得更加容易。基于最大流定理上的最大流算法•如果残留网络上找不到可增广路径，则当前流为最大流；反之，如果当前流不为最大流，则残留网络上一定有可增广路径。•计算最大流的关键在于怎样找出可增广路经。寻找一条可增广路径的常用方法有3种：DFS，BFS，标号搜索（PFS）初始化一个可行流：对所有u,v∈Vf(u,v)←0现有网络流的残留网络上有增广路径吗？按上面方法对增广路径进行改进F为最大流Dinic算法•Dinic算法的基本思路是分阶段地在层次图中改进流量。层次图是在残留网络的基础上对每个节点加一个层次标记level，标出该节点到源点的距离。显然，源点的level为0。•由节点的层次引出了层次图D3=（V3，E3）的概念：对于残留网络D2=（V2，E2）中的一条边（u,v），当且仅当level（u）+1=level（v）时，边（u,v）∈E3；V3=｛v|E3中边与u相连｝。也就是说，在程序实现的时候，层次图并不是构建出来的，而是对每个节点标记层次，扩展可增广路径时只需判断边（u,v）是否满足约束条件level（u）+1=level（v）即可。Dinic算法的基本流程由流程图可以看出，算法呈循环结构。每一次循环为一个阶段。在每个阶段中，首先根据残留网络建立层次图（一般采用BFS算法建立层次图），然后用DFS过程在层次图内扩展可增广路径，调整流量。增广完毕后，进入下一个阶段。这样不断重复，直到汇点不在层次图内出现为止。汇点不在层次图内意味着残留网络中不存在从源点到汇点的路径，即没有可增广路径。对于有n个节点的网络流图，Dinic算法最多有n个阶段。初始化网络流图根据残留网络计算层次图汇点不在层次图内在层次图内用一次DFS过程改进流量算法结束是否Dinic递归版programmaxflow_Dinic;typeedge=recordy,r,next,op:longint;end;varg:array[1..400]ofedge;level,q,h:array[1..200]oflongint;n,m,i,ans,a,b,c,tot,vs,vt:longint;procedureadd(a,b,c:longint);begininc(tot);g[tot].y:=b;g[tot].r:=c;g[tot].next:=h[a];h[a]:=tot;g[tot].op:=tot+1;inc(tot);g[tot].y:=a;g[tot].r:=0;g[tot].next:=h[b];h[b]:=tot;g[tot].op:=tot-1;end;functionbfs:boolean;vari,f,r,tmp,v,u:longint;beginfillchar(level,sizeof(level),0);f:=1;r:=1;q[f]:=vs;level[vs]:=1;repeatv:=q[f];tmp:=h[v];whiletmp-1dobeginu:=g[tmp].y;if(g[tmp].r0)and(level[u]=0)thenbeginlevel[u]:=level[v]+1;inc(r);q[r]:=u;ifu=vtthenexit(true);end;tmp:=g[tmp].next;end;inc(f);untilfr;exit(false);end;functiondfs(v,a:longint):longint;varans,flow,tmp,u,value:longint;beginif(v=vt)or(a=0)thenexit(a);ans:=0;tmp:=h[v];whiletmp-1dobeginu:=g[tmp].y;value:=g[tmp].r;if(level[u]=level[v]+1)thenbeginflow:=dfs(u,min(a,value));ifflow0thenbeging[tmp].r:=g[tmp].r-flow;g[g[tmp].op].r:=g[g[tmp].op].r+flow;ans:=ans+flow;a:=a-flow;ifa=0thenbreak;end;end;tmp:=g[tmp].next;end;exit(ans);end;beginfillchar(h,sizeof(h),$ff);readln(n,m);tot:=0;ans:=0;vs:=1;vt:=m;fori:=1tondobeginreadln(a,b,c);add(a,b,c);end;whilebfsdobeginans:=ans+dfs(1,maxlongint);end;writeln(ans);end.•Poj1273DrainageDitches•Poj3281Dining•Poj1149Pigs•Poj1459PowerNetwork•POJ1698最大流最小割定理•图的割：对于某个顶点集合SV，从S出发指向S外部的那些边的集合，记为割（S，V\S）。这些边的容量之和被称为割的容量•S-t割：如果sS，tV\S，那么此时的割称为s-t割•最小割问题：对于给定网络，为了保证没有从s到t的路径，需要删除的边的总容量值最小最大权闭合子图•给定带权图G（权值可正可负），求一个权和最大的点集，使得起点在该点集中的任意弧，终点也在该点集中。•解：新增附加源s和附加汇t，从s向所有正权点引一条边，容量为权值；从所有负权边向汇点引一条边，容量为权值的相反数。求出最小割以后，S-{s}就是最大闭合子图。最大密度子图•给出一个无向图，找一个点集，使得这些点之间的边数除以点数的值（称为子图的密度）最大。•POJ3469DualCoreCPU•POJ2987Firing（最大权闭合图）•POJ3155HardLife（最大密度子图）最小费用最大流“流”的问题可能不仅仅是流量，还包括“费用”的因素。网络的每一条边（Vi，Vj）除给定了容量Cij外，还给了一个单位流量费用Bij=0。问题的数学模型是求最大流F，使流的总输送费用B（F）=∑BijFij（I,j∈A）取极小值。这就是所谓的最小费用最大流问题。右图所示是一个公路网，s是仓库所在地，t是物资终点。每一条边都有两个数字，第一个数字表示某段时间通过公路的物资的最多吨数，第二个数字表示每顿物资通过该公路的费用。问怎样安排才能即使得从s运到t的物资最多，又使得总的运输费用最少？算法思想•从F=0开始，设已知F是流量V（F）的最小费用流，余下的问题是如何去寻求关于F的最小费用可增广路径。•构造一个加权有向图W（F），它的节点是原网络D的节点，把D中的每一条边（Vi，Vj）变成两个方向相反的边Vi,Vj和Vj,Vi。定义W（F）中的边权Wij为•于是在网络中寻求关于F的最小费用可增广路径，等价于在加权有向图W（F）中寻求从Vs到Vt的最短路径。算法思想•代码实现programmincost;constmaxn=1000;maxm=1000*1000*2;typeedge=recordu,v,r,c,next,op:longint;end;varg:array[1..maxm]ofedge;h:array[1..maxn]oflongint;s,t,flow,cost,a,b,c,d,tot,n,m,i:longint;beginfillchar(h,sizeof(h),$ff);readln(n,m);fori:=1tomdobeginreadln(a,b,c,d);add(a,b,c,d);end;flow:=0;cost:=0;s:=1;t:=n;whilespfa(s,t,flow,cost)do;writeln(flow,'',cost);end.procedureadd(u,v,r,c:longint);begininc(tot);g[tot].u:=u;g[tot].v:=v;g[tot].r:=r;g[tot].c:=c;g[tot].next:=h[u];h[u]:=tot;g[tot].op:=tot+1;inc(tot);g[tot].u:=v;g[tot].v:=u;g[tot].r:=0;g[tot].c:=-c;g[tot].next:=h[v];h[v]:=tot;g[tot].op:=tot-1;end;functionspfa(s,t:longint;varflow,cost:longint):boolean;vard,p,a:array[1..maxn]oflongint;inq:array[1..maxn]ofboolean;q:array[1..maxm]oflongint;i,u,v,tmp,f,r:longint;beginfillchar(d,sizeof(d),$7f);fillchar(inq,sizeof(inq),false);d[s]:=0;inq[s]:=true;p[s]:=0;a[s]:=maxlongint;f:=1;r:=1;q[f]:=1;repeatu:=q[f];tmp:=h[u];whiletmp-1dobeginv:=g[tmp].v;if(g[tmp].r0)and(d[v]d[u]+g[tmp].c)thenbegind[v]:=d[u]+g[tmp].c;p[v]:=tmp;a[v]:=min(a[u],g[tmp].r);ifnotinq[u]thenbegininc(r);q[r]:=u;inq[u]:=true;end;end;tmp:=g[tmp].next;end;inc(f);inq[u]:=false;untilfr;ifd[t]=maxlongintthenexit(false);flow:=flow+a[t];cost:=cost+d[t]*a[t];u:=t;while(us)dobeging[p[u]].r:=g[p[u]].r-a[t];g[g[p[u]].op].r:=g[g[p[u