11-最大流问题

《11-最大流问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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)。流的平衡条件：

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

3、s到t的一条路，若p满足下述两个条件，则称p是关于可行流F的一条可增广路径，亦称可改进路径：在p+的所有前向弧（u,v）上，0<=f(u,v)

4、u)；去除“剩余流量”为0的弧。在这样的图上找可增广路经变得更加容易。基于最大流定理上的最大流算法如果残留网络上找不到可增广路径，则当前流为最大流；反之，如果当前流不为最大流，则残留网络上一定有可增广路径。计算最大流的关键在于怎样找出可增广路经。寻找一条可增广路径的常用方法有3种：DFS，BFS，标号搜索（PFS）初始化一个可行流：对所有u,v∈Vf(u,v)←0现有网络流的残留网络上有增广路径吗？按上面方法对增广路径进行改进F为最大流Dinic算法Dinic算法的基本思路是分阶段地在层次图中改进流量。层次图是在残留网络

5、的基础上对每个节点加一个层次标记level，标出该节点到源点的距离。显然，源点的level为0。由节点的层次引出了层次图D3=（V3，E3）的概念：对于残留网络D2=（V2，E2）中的一条边（u,v），当且仅当level（u）+1=level（v）时，边（u,v）∈E3；V3=｛v

6、E3中边与u相连｝。也就是说，在程序实现的时候，层次图并不是构建出来的，而是对每个节点标记层次，扩展可增广路径时只需判断边（u,v）是否满足约束条件level（u）+1=level（v）即可。Dinic算法的基本流程由流程图可以看出，算法呈循

7、环结构。每一次循环为一个阶段。在每个阶段中，首先根据残留网络建立层次图（一般采用BFS算法建立层次图），然后用DFS过程在层次图内扩展可增广路径，调整流量。增广完毕后，进入下一个阶段。这样不断重复，直到汇点不在层次图内出现为止。汇点不在层次图内意味着残留网络中不存在从源点到汇点的路径，即没有可增广路径。对于有n个节点的网络流图，Dinic算法最多有n个阶段。初始化网络流图根据残留网络计算层次图汇点不在层次图内在层次图内用一次DFS过程改进流量算法结束是否Dinic算法实现数据结构constmaxn=1000;maxm=1

8、00000;maxw=2000000000;typegtype=recordx,y,f,c,next,op:longint;end;varg:array[1..maxm*2]ofgtype;first,first1:array[1..maxn]oflongint;p,level,prt:array[1..maxn]oflongint;visited:array[1..maxn]ofboolean;n,m,tot,vs,vt,maxflow,temp,i,a,b,c:longint;1、建图procedureadd(a,b

9、,c:longint);begininc(tot);g[tot].x:=a;g[tot].y:=b;g[tot].c:=c;g[tot].next:=first[a];first[a]:=tot;g[tot].op:=tot+1;inc(tot);g[tot].x:=b;g[tot].y:=a;g[tot].c:=0