11-最大流问题.ppt

1、最大流问题,陈旭龙,在一个单源单汇的简单有向图引入流量因素，且要求计算满足流量限制和平衡条件的最大可行流时，就产生了最大流问题。,基本概念,（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的“流量”相等。

2、 （3）网络的流量V(F)：指源点的净流出流量和汇点的净流入流量。,寻找网络G上可能的最大流量即为网络G上的最大流问题,在可增广路径的基础上计算最大流,最大流算法的核心是计算可增广路径,可增广路径的基本概念,退流的概念和弧的分类 若p是网络中连接源点s和汇点t的一条路，且路的方向是从s到t的，则路上的弧有前向弧和后向弧两种。 前向弧：弧的方向与路的方向一致。前向弧的全体记为p+ 后向弧：弧的方向与路的方向相反。后向弧的全体记为p-,可增广路径的定义,设F是一个可行流，p是从s到t的一条路，若p满足下述两个条件，则称p是关于可行流F的一条可增广路径，亦称可改进路径： 在p+的所有前向弧（u,v）

3、上，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的弧。在这样的图上找可增广路经变得更加容易。,基于最大流定理上的最大流算法,如果残留网络上找不到可增广路径，则当前流为最大流；反之，如果当前流不为最大流，则残留网络

4、上一定有可增广路径。 计算最大流的关键在于怎样找出可增广路经。寻找一条可增广路径的常用方法有3种：DFS，BFS，标号搜索（PFS）,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相连。也就是说，在程序实现的时候，层次图并不是构建出来的，而是对每个节点标记层次，扩

5、展可增广路径时只需判断边（u,v）是否满足约束条件level（u）+1=level（v）即可。,Dinic算法的基本流程,由流程图可以看出，算法呈循环结构。每一次循环为一个阶段。在每个阶段中，首先根据残留网络建立层次图（一般采用BFS算法建立层次图），然后用DFS过程在层次图内扩展可增广路径，调整流量。增广完毕后，进入下一个阶段。这样不断重复，直到汇点不在层次图内出现为止。汇点不在层次图内意味着残留网络中不存在从源点到汇点的路径，即没有可增广路径。对于有n个节点的网络流图，Dinic算法最多有n个阶段。,Dinic算法实现,数据结构,const maxn=1000; maxm=100000;

6、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.

7、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

8、:=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; va

9、r 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.f-1 do begin if (not visitedgtemp.y) and (levelg

10、temp.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

11、); 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

12、算法最多有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;,proce

13、dure 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;

14、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) o

15、r (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);

16、 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(二分图匹配) 草地排水 P1635 植物大战僵尸 P1774

17、 南湖探险,最小费用最大流,“流”的问题可能不仅仅是流量，还包括“费用”的因素。网络的每一条边（Vi，Vj）除给定了容量Cij外，还给了一个单位流量费用Bij=0。问题的数学模型是求最大流F，使流的总输送费用B（F）=Bij Fij （I,jA）取极小值。这就是所谓的最小费用最大流问题。,右图所示是一个公路网，s是仓库所在地，t是物资终点。每一条边都有两个数字，第一个数字表示某段时间通过公路的物资的最多吨数，第二个数字表示每顿物资通过该公路的费用。问怎样安排才能即使得从s运到t的物资最多，又使得总的运输费用最少？,算法思想,从F=0开始，设已知F是流量V（F）的最小费用流，余下的问题是如何去寻

18、求关于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,

19、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