最大流算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,网络流初步,最大流算法,最小费用最大流,最大流最小割定理,最大流算法,网络流之一,问题：问从,S,到,T,的最大水流量是多少？,1 S,4,3,2,5,6,t,7,3,4,8,4,2,4,6,实例：,有一自来水管道输送系统，起点是,S,，目标是,T,，途中经过的管道都有一个最大的容量。,1 S,4,3,2,5,6,t,7,3,4,8,4,2,4,6,4,6,2,2,2,4,4,6,最大水流量是,10,一、网络流的定义,有唯一的一个,源点,S,（入度为,0,：出发点）,有唯一的一个,汇点,T,（出度为,0,：结束点）,图中每条弧,(u, v),都有一,非负,容量,c ( u, v ),有向图,G = ( V, E ),中：,满足上述条件的图,G,称为网络流图。,记为：,G = ( V, E,，,C),1,、可行流,每条弧,( u, v ),上 给定一个实数,f(u,v,),满足：有,0 = f ( u, v ) = c( u, v ),则,f(u,v,),称为弧,( u, v ),上的流量。,如果有一组流量满足,条件：,源点,s,：,流出量,=,整个网络的流量,汇点,t,：,流入量,=,整个网络的流量,中间点：总流入量,=,总流出量,那么整个网络中的流量成为一个可行流。,区分：容量和流量,1,2,4,3,5,6,4,2,3,4,5,4,1,2,1,2,4,3,5,4,2,3,3,3,1,1,2,4,3,5,6,4,2,3,4,5,4,1,1,2,4,3,5,4,2,3,5,3,3,3,4,一个可行流：,5,一个可行流：,7,图,1,图,2,2,、最大流,在所有的可行流中， 流量最大的一个流的流量,如： 图,2,中可行流,7,也是最大流。,最大流可能不只一个。,二、最大流算法,步骤：,（,1,）如果存在增广路径,就找出一条增广路径,（,2,）然后沿该条增广路径进行更新流量,（增加流量）,Ford-Fulkerson,（福特,-,福克森）算法：,1,、增广路径,从,s,到,t,的一条简单路径，若边,( u, v ),的方向与该路径的方向一致，称,( u, v ),为正向边，方向不一致时称为逆向边。,简单路：,1,3 245,中。,（,1,，,3,）（,2,，,4,）,（,4,，,5,）,是正向边。（,3,，,2,）是逆向边。,1,2,4,3,5,6,4,2,3,4,5,1,2,4,3,5,6,4,2,3,4,5,若路径上所有的边满足：,所有正向边有：,f ( u, v ) 0,则称该路径为一条,增广路径,(,可增加流量,),增广路径：,两条增广路径：,1,35,13 245,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,增加流量,=,？,2,、沿增广路径增广,1,） 先设,d,为为,正无穷,(,可增加流，余流量,),若,( u, v ),是正向边,d = min ( d, c ( u, v ) f (u, v ) ),若,( u, v ),是逆向边,d = min ( d, f ( u, v ) ),2,） 对与该增广路径上的边,若,( u, v ),是正向边，,f ( u, v ) = f ( u, v ) + d;,若,( u, v ),是逆向,边，,f ( u, v ) = f ( u, v ) d;,增广后，总流量增加了,d,1,2,4,3,5,6,4,2,3,4,5,样例：,开始流量为,:sum=0,1,、一条增广路径,:,1,235,d=min4,2,4 =2,增加流量,: 2,Sum=2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,、一条增广路径,:,1,245,d=min4-2,3,5 =2,增加流量,: 2,Sum=2+2=4,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2-1=1,2,1,2,4,3,5,4,2,3,4,5,2,2,2,3,、一条增广路径,:,1,2 4 5,d=min6,2,3-2,5-2 =1,增加流量,: 1,Sum=4+1=5,1,1,1,2-3,减少，加到,-,-3,减的由,-,补充,4,、一条增广路径,:,1,5,d=min6-1,4-2 =2,增加流量,: 2,Sum=5+2=7,1,2,4,3,5,6,4,2,3,4,5,2,2-1=1,2,1,2,4,3,5,4,2,3,4,2,2,2,1,1,1,1,2,4,3,5,6,4,2,3,4,5,2,2-1=1,2,1,2,4,3,5,4,2,3,4,5,2,2,2,1,1,1,2,2,定理：,可行流,f,为最大流，当且仅当不存在关于,f,的增广路径,证：若,f,是最大流，但图中存在关于,f,的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与,f,是最大流矛盾。所以，最大流不存在增广路径。,Ford-Fulkerson,方法,(,增广流,),求最大流,（福特,-,福克森）,步骤：（,1,）如果存在增广路径,就找出一条增广路径,DFS,BFS,（,2,）然后沿该条增广路径进行更新流量,（增加流量）,While,有增广路径,do,更新该路径的流量,迭代算法,c u, v ,：容量,f u, v ,：流量,Bi,：保存找到的增广路径，记录路径上结点,i,的前驱结点。,Sum,：最大流量。,假定：,1,是源点,S,；,n,是汇点,T,。,算法的实现：,function,findflow(k:integer):boolean,; ,找结点,k,的后继结点,i ,var,i:integer,;,begin,if k=n then,exit(true,); ,找到了一条增广路径,for i:=1 to n do,if(bi,=-1),and(ck,i-fk,i,0)or(fi,k0) then,begin,bi,:=k;,if,findflow(i,) then,exit(true,);,end;,exit(false,);,end;,1,）：,DFS,找增广路径,2,）,procedure,addflow,;/,沿增广路径增广（增加流量）,d:=,maxint,; ,增量,i:=n; ,沿增广路径的终点向起点反向求,d,while,bi,0 do,begin,if,cbi,i,0 then d:=,min(d,cbi,i-fbi,i,); ,正向边,if,ci,bi,0 then d:=,min(d,fi,bi,); ,逆向边,i:=,bi,;,end;,i:=n;,while,bi,0 do ,逆向更新每条边的流量, begin,if,cbi,i,0 then,inc(fbi,i,d,);,正向边,if,ci,bi,0 then,dec(fi,bi,d,);,逆向边,i:=,bi,;,end;,inc(sum,d,); ,总流量增加,d,主程序：,for i:=1 to n do,bi,:= -1; ,初始化增广路径,b1:=0;,while findflow(1) do ,增广流,begin,addflow,;,for i:=1 to n do,bi,:=-1;,b1:=0;,end;,writeln(sum,); ,输出最大流,for i:=1 to n do ,输出每条边的流量,for j:=1 to n do,if,fi,j,0 then,writeln(i,-,j, ,fi,j,);,优化,残留网络,d,的设置：,若存在,( u, v ),则,d ( u, v ) = c ( u, v ) f ( u, v ),d ( v, u ) = f ( u, v ),d ( u, v ),是 从,u,到,v,能增加的最大流量,理解,:,(,u,v,),的流量为,f(u,v,),作为正向边还可以增加的量是,c ( u, v ) f ( u, v ),，作为逆向边，还可以增加的流量为：,f ( u, v ),。,增广路上正向边流量增加，逆向边增加流量减少。,1,2,4,3,5,6,4,2,3,4,5,2,2,2,1,2,4,3,5,6,4,2,3,4,5,2,2,2,d ( u, v ) = c ( u, v ),d ( v, u ) = 0,深搜找增广路径过程,function find( k:integer ):,boolean,;,if k=n then exit(true);,for i:=1 to n do,if (bi= -1) and (dk,i0) then,bi:=k;,if find(i) then exit(true);,/,此处,bi,不需要变回,-1,exit(false);,/ b1=0; b2 n= -1;,主,函数中调用,find(1),广搜找增广路径过程,function,bfsbfs:boolean,; a,是广搜队列,for i:=1 to n do bi:=-1; b,是,前驱,b1:=0; a1:=1; open:=0; closed:=1;,while open0) then,inc(closed,); aclosed:=i; bi:=k;,if i=n then exit(true);,找到增广路,exit(false);,没找到增广路,增广过程,min:=,maxint,;,i:=n;,while bi0 (i1) do /,逆向求增加流,min,if mindbi,i then min:=dbi,i;,i:=,bi,;,i:=n;,while bi0 (i1) do/ /,逆向修改流量,dec(dbi,i,min,); inc(di,bi,min);,i:=,bi,;,inc(sum,min); sum,是总流量,问题,1,：奶牛的新年晚会,奶牛们要举办一次别开生面的新年晚会。每头奶牛会做一些不同样式的食品（单位是盘）。到时候他们会把自己最拿手的不超过,k,样食品各做一盘带到晚会，和其他奶牛一起分享。但考虑到食品太多会浪费掉，他们给每种食品的总盘数都规定了一个不一定相同的上限值。这让他们很伤脑筋，究竟应该怎样做，才能让晚会上食品的总盘数尽量的多呢？,例如：有,4,头奶牛，每头奶牛最多可以带,3,盘食品。一共有,5,种食品，它们的数量上限是,2,、,2,、,2,、,2,、,3,。奶牛,1,会做食品,14,，奶牛,2,会做食品,25,，奶牛,3,会做食品,1,、,2,、,4,，奶牛,4,会做食品,13,。那么最多可以带,9,盘食品到晚会上。即奶牛,1,做食品,24,，奶牛,2,做食品,35,，奶奶,3,做食品,1,、,2,，奶牛,4,做食品,1,。这样，,4,种食品各有,2,、,2,、,2,、,2,、,1,盘。,1,2,3,4,1,2,3,4,5,奶牛,食品,S,3,3,3,3,T,2,2,2,2,3,权,=1,边：,S,奶牛,保证每头奶牛带的食品的最大量。,边：食品,T,保证每种食品的最大数量。,食品的总盘数最大值,=S,到,T,的最大流,1,2,3,4,1,2,3,4,5,奶牛,食品,S,3,3,3,3,T,2,2,2,2,3,权,=1,S,到,T,的最大流,=9,应用,求,二分图的,最大匹配,利用网络流建模,所有边的容量都是,1,