最大流算法ppt课件.ppt

网络流初步,最大流算法 最小费用最大流 最大流最小割定理,最大流算法,网络流之一,问题：问从S到T的最大水流量是多少？,实例：,有一自来水管道输送系统，起点是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：流入量=整个网络的流量 中间点：总流入量=总流出量 那么整个网络中的流量成为一个可行流。,区分：容量和流量,一个可行流：5,一个可行流：7,图1,图2,2、最大流,在所有的可行流中，流量最大的一个流的流量 如：图2中可行流7也是最大流。最大流可能不只一个。,二、最大流算法,步骤：（1）如果存在增广路径,就找出一条增广路径（2）然后沿该条增广路径进行更新流量（增加流量）,Ford-Fulkerson（福特-福克森）算法：,1、增广路径,从 s 到 t 的一条简单路径，若边(u,v)的方向与该路径的方向一致，称(u,v)为正向边，方向不一致时称为逆向边。,简单路：13 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则称该路径为一条增广路径(可增加流量),增广路径：,两条增广路径：13513 245,增加流量=？,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,样例：,开始流量为:sum=0,1、一条增广路径:1235d=min4,2,4=2 增加流量:2Sum=2,2、一条增广路径:1245d=min4-2,3,5=2 增加流量:2Sum=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-1=1,2,1,2,4,3,5,4,2,3,4,5,2,2,2,3、一条增广路径:1 2 4 5d=min6,2,3-2,5-2=1 增加流量:1Sum=4+1=5,1,1,1,2-3减少，加到-3减的由-补充,4、一条增广路径:1 5d=min6-1,4-2=2 增加流量:2Sum=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,定理：可行流 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,i0)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 bi0 do begin if cbi,i0 then d:=min(d,cbi,i-fbi,i);正向边 if ci,bi0 then d:=min(d,fi,bi);逆向边 i:=bi;end;i:=n;while bi0 do 逆向更新每条边的流量 begin if cbi,i0 then inc(fbi,i,d);正向边 if ci,bi0 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,j0 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)。增广路上正向边流量增加，逆向边增加流量减少。,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盘。,奶牛,食品,边：S奶牛,保证每头奶牛带的食品的最大量。边：食品T,保证每种食品的最大数量。食品的总盘数最大值=S到T的最大流,奶牛,食品,S到T的最大流=9,应用,求二分图的最大匹配 利用网络流建模 所有边的容量都是1,