11-最大流问题.ppt

最大流问题陈旭龙 在一个单源单汇的简单有向图引入流量因素，且要求计算满足流量限制和平衡条件的最大可行流时，就产生了最大流问题。基本概念（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,vV f(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算法实现 数据结构const maxn=1000; maxm=100000; maxw=2000000000;type gtype=record x,y,f,c,next,op:longint; end;var g:array1.maxm*2 of gtype; first,first1:array1.maxn of longint; p,level,prt:array1.maxn of longint; visited:array1.maxn of boolean; n,m,tot,vs,vt,maxflow,temp,i,a,b,c:longint;1、建图procedure add(a,b,c:longint);begin inc(tot); gtot.x:=a; gtot.y:=b; gtot.c:=c; gtot.next:=firsta; firsta:=tot; gtot.op:=tot+1; inc(tot); gtot.x:=b; gtot.y:=a; gtot.c:=0; gtot.next:=firstb; firstb:=tot; gtot.op:=tot-1;end;2、通过BFS计算层次图的层次procedure make_level;var i,f,r,temp,tp:longint;begin for i:=1 to n do leveli:=maxw; fillchar(p,sizeof(p),0); f:=1; r:=1; pf:=vs; levelvs:=1; repeat tp:=pf; if tp=vt then exit; temp:=firsttp; while temp-1 do begin if levelgtemp.yleveltp+1 then if (gtemp.f0) then begin inc(r); pr:=gtemp.y; levelgtemp.y:=leveltp+1; end; temp:=gtemp.next; end; inc(f); until fr;end;3、在层次图内扩展可增广路径，调整流量procedure dfs_maxflow;var top,mint,i,temp,tp,ti:longint;begin fillchar(p,sizeof(p),0); fillchar(prt,sizeof(prt),0); fillchar(visited,sizeof(visited),false); first1:=first; top:=1; p1:=vs; while top0 do begin if ptop=vt then begin mint:=maxw; for i:=top downto 2 do if gprtpi.fgprtpi.c then mint:=min(mint,gprtpi.c-gprtpi.f) else mint:=min(mint,gprtpi.f); for i:=top downto 2 do if gprtpi.fgprtpi.c then begin gprtpi.f:=gprtpi.f+mint; ggprtpi.op.f:=ggprtpi.op.f+mint; if gprtpi.f=gprtpi.c then ti:=i; end else begin gprtpi.f:=gprtpi.f-mint; ggprtpi.op.f:=ggprtpi.op.f-mint; if gprtpi.f=0 then ti:=i; end; top:=ti-1; end else begin temp:=first1ptop; tp:=ptop; while temp-1 do begin if (not visitedgtemp.y) and (levelgtemp.y=leveltp+1) then if (gtemp.f0) then begin first1ptop:=gtemp.next; inc(top); ptop:=gtemp.y; prtptop:=temp; break; end; temp:=gtemp.next; end; if temp=-1 then begin visitedptop:=true; dec(top); end; end; end;end;4、主程序begin fillchar(g,sizeof(g),0); readln(n,m); fillchar(first,sizeof(first),$ff); tot:=0; for i:=1 to m do begin readln(a,b,c); add(a,b,c); end; vs:=1; vt:=n; while true do begin make_level; if levelvt=maxw then break; dfs_maxflow; end; maxflow:=0; temp:=firstvs; while temp-1 do begin maxflow:=maxflow+gtemp.f; temp:=gtemp.next; end; writeln(maxflow);end.对于n个节点、m条边的网络流图，Dinic算法最多有n个阶段，即最多构建n个层次图，每个层次图用BFS一次遍历即可得到。一次BFS遍历的复杂度为O(m)，所有构建层次图的总时间为O(nm)；一次DFS的时间复杂度为O(mn)，因为最多进行n此DFS，所以找可增广路径共需时间O(m*n*n)。Dinic递归版program maxflow_Dinic;type edge=record y,r,next,op:longint; end;var g:array1.400 of edge; level,q,h:array1.200 of longint; n,m,i,ans,a,b,c,tot,vs,vt:longint;procedure add(a,b,c:longint);begin inc(tot); gtot.y:=b; gtot.r:=c; gtot.next:=ha; ha:=tot; gtot.op:=tot+1; inc(tot); gtot.y:=a; gtot.r:=0; gtot.next:=hb; hb:=tot; gtot.op:=tot-1;end;function bfs:boolean;var i,f,r,tmp,v,u:longint;begin fillchar(level,sizeof(level),0); f:=1; r:=1; qf:=vs; levelvs:=1; repeat v:=qf; tmp:=hv; while tmp-1 do begin u:=gtmp.y; if (gtmp.r0) and (levelu=0) then begin levelu:=levelv+1; inc(r); qr:=u; if u=vt then exit(true); end; tmp:=gtmp.next; end; inc(f); until fr; exit(false);end;function dfs(v,a:longint):longint;var ans,flow,tmp,u,value:longint;begin if (v=vt) or (a=0) then exit(a); ans:=0; tmp:=hv; while tmp-1 do begin u:=gtmp.y; value:=gtmp.r; if (levelu=levelv+1) then begin flow:=dfs(u,min(a,value); if flow0 then begin gtmp.r:=gtmp.r-flow; ggtmp.op.r:=ggtmp.op.r+flow; ans:=ans+flow; a:=a-flow; if a=0 then break; end; end; tmp:=gtmp.next; end; exit(ans);end;begin fillchar(h,sizeof(h),$ff); readln(n,m); tot:=0; ans:=0; vs:=1; vt:=m; for i:=1 to n do begin readln(a,b,c); add(a,b,c); end; while bfs do begin ans:=ans+dfs(1,maxlongint); end; writeln(ans);end. poj1273 Poj1149 Poj1459 poj2239(二分图匹配二分图匹配) Poj1087(二分图匹配二分图匹配) Poj1325(二分图匹配二分图匹配) 草地排水草地排水http:/ P1635 植物大战僵尸 P1774 南湖探险 最小费用最大流“流”的问题可能不仅仅是流量，还包括“费用”的因素。网络的每一条边（Vi，Vj）除给定了容量Cij外，还给了一个单位流量费用Bij=0。问题的数学模型是求最大流F，使流的总输送费用B（F）=Bij Fij （I,jA）取极小值。这就是所谓的最小费用最大流问题。右图所示是一个公路网，s是仓库所在地，t是物资终点。每一条边都有两个数字，第一个数字表示某段时间通过公路的物资的最多吨数，第二个数字表示每顿物资通过该公路的费用。问怎样安排才能即使得从s运到t的物资最多，又使得总的运输费用最少？算法思想 从F=0开始，设已知F是流量V（F）的最小费用流，余下的问题是如何去寻求关于F的最小费用可增广路径。 构造一个加权有向图W（F），它的节点是原网络D的节点，把D中的每一条边（Vi，Vj）变成两个方向相反的边和。定义W（F）中的边权Wij为 于是在网络中寻求关于F的最小费用可增广路径，等价于在加权有向图W（F）中寻求从Vs到Vt的最短路径。算法思想代码实现program mincost;const maxn=1000; maxm=1000*1000*2;type edge=record u,v,r,c,next,op:longint; end;var g:array1.maxm of edge; h:array1.maxn of longint; s,t,flow,cost,a,b,c,d,tot,n,m,i:longint;begin fillchar(h,sizeof(h),$ff); readln(n,m); for i:=1 to m do begin readln(a,b,c,d); add(a,b,c,d); end; flow:=0; cost:=0; s:=1; t:=n; while spfa(s,t,flow,cost) do; writeln(flow, ,cost);end.procedure add(u,v,r,c:longint);begin inc(tot); gtot.u:=u; gtot.v:=v; gtot.r:=r; gtot.c:=c; gtot.next:=hu; hu:=tot; gtot.op:=tot+1; inc(tot); gtot.u:=v; gtot.v:=u; gtot.r:=0; gtot.c:=-c; gtot.next:=hv; hv:=tot; gtot.op:=tot-1;end;function spfa(s,t:longint;var flow,cost:longint):boolean;var d,p,a:array1.maxn of longint; inq:array1.maxn of boolean; q:array1.maxm of longint; i,u,v,tmp,f,r:longint;begin fillchar(d,sizeof(d),$7f); fillchar(inq,sizeof(inq),false); ds:=0; inqs:=true; ps:=0; as:=maxlongint; f:=1; r:=1; qf:=1; repeat u:=qf; tmp:=hu; while tmp-1 do begin v:=gtmp.v; if (gtmp.r0) and (dvdu+gtmp.c) then begin dv:=du+gtmp.c; pv:=tmp; av:=min(au,gtmp.r); if not inqu then begin inc(r); qr:=u; inqu:=true; end; end; tmp:=gtmp.next; end; inc(f); inqu:=false; until fr; if dt=maxlongint then exit(false); flow:=flow+at; cost:=cost+dt; u:=t; while (us)do begin gpu.r:=gpu.r-at; ggpu.op.r:=ggpu.op.r+at; u:=gpu.u; end; exit(true);end;最小费用最大流 Wikioi 1914 运输问题 Wikioi 1033 蚯蚓的游戏问题 Zoj1231 poj2159