最大流算法ppt课件.ppt

《最大流算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《最大流算法ppt课件.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统网络流初步网络流初步篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 最大流算法最大流算法 最小费用最大流最小费用最大流 最大流最小割定理最大流最小割定理篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统最大流算法最大流算法网络流之一网络流之一篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统问题：问从S到T的最大

2、水流量是多少？1 S43256 t7 3484246实例：有一自来水管道输送系统，起点是S，目标是T，途中经过的管道都有一个最大的容量。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 1 S43256 t7 348424646222446最大水流量是10篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统一、网络流的定义有唯一的一个源点S（入度为0：出发点）有唯一的一个汇点 T（出度为0：结束点）图中每条弧(u,v)都有一非负容量 c(u,v)有向图 G=(V,E)中：满足上述

3、条件的图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：流入量=整个网络的流量 中间点：总流入量=总流出量 那么整个网络中的流量成为一个可行流。区分：容量和流量篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统124356423454121

4、243542333112435642345411243542353334一个可行流：5一个可行流：7图1图2篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、最大流在所有的可行流中，流量最大的一个流的流量 如：图2中可行流7也是最大流。最大流可能不只一个。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统二、最大流算法二、最大流算法步骤：（1）如果存在增广路径,就找出一条增广路径 （2）然后沿该条增广路径进行更新流量 （增加流量）Ford-Fulkerson（福特-福克森）算

5、法：篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1、增广路径、增广路径从从 s 到到 t 的一条简单路径，若边的一条简单路径，若边(u,v)的方向与的方向与该路径的方向一致，称该路径的方向一致，称(u,v)为正向边，方向不为正向边，方向不一致时称为逆向边。一致时称为逆向边。简单路：简单路：13 245中。中。（1，3）（）（2，4）（4，5）是正向边。（是正向边。（3，2）是逆向边。）是逆向边。1243564234512435642345篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种

6、得分类型的系统若路径上所有的边满足：若路径上所有的边满足：所有正向边有：所有正向边有：f(u,v)c(u,f(u,v)0f(u,v)0则称该路径为一条则称该路径为一条增广路径增广路径(可增加流量可增加流量)增广路径：两条增广路径：两条增广路径：13513 2451243564234522212435642345222增加流量增加流量=？篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、沿增广路径增广、沿增广路径增广 1）先设d为为正无穷(可增加流，余流量)若(u,v)是正向边 d =min(d,c(u,v)f(u,v)若(u,v)是

7、逆向边 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篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统12435642345样例：样例：开始流量为开始流量为:sum=0篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1、一条增广路径、一条增广路径:1235d=min4,2,4=2 增加流量增加流量:2Sum=2124356423452221

8、2435642345篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2、一条增广路径、一条增广路径:1245d=min4-2,3,5=2 增加流量增加流量:2Sum=2+2=4124356423452221243564234522212435642345222篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统12435642345222124356423452221243564234522-1=1212435423452223、一条增广路径、一条增广路径:1 2 4 5d=mi

9、n6,2,3-2,5-2=1 增加流量增加流量:1Sum=4+1=51112-3减少，加到减少，加到-3减的由减的由-补充补充篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统4、一条增广路径、一条增广路径:1 5d=min6-1,4-2=2 增加流量增加流量:2Sum=5+2=71243564234522-1=121243542342221111243564234522-1=12124354234522211122篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统定理：可行流

10、f 为最大流，当且仅当不存在关于f 的增广路径 证：若 f 是最大流，但图中存在关于 f 的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f 是最大流矛盾。所以，最大流不存在增广路径。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统Ford-Fulkerson方法(增广流)求最大流（福特-福克森）步骤：（1）如果存在增广路径,就找出一条增广路径 DFS,BFS（2）然后沿该条增广路径进行更新流量 （增加流量）While 有增广路径 do 更新该路径的流量迭代算法篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因

11、此，篮球比赛的计时计分系统是一种得分类型的系统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

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

13、);正向边 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 增广流

14、 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),作为正

15、向边还可以增加的量是c(u,v)f(u,v)，作为逆向边，还可以增加的流量为：f(u,v)。增广路上正向边流量增加，逆向边增加流量减少。1243564234522212435642345222 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

16、 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(f

17、alse);没找到增广路篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统 增广过程 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：奶牛的新年晚会 奶

18、牛们要举办一次别开生面的新年晚会。每头奶牛会做奶牛们要举办一次别开生面的新年晚会。每头奶牛会做一些不同样式的食品（单位是盘）。到时候他们会把自己最一些不同样式的食品（单位是盘）。到时候他们会把自己最拿手的不超过拿手的不超过k k样食品各做一盘带到晚会，和其他奶牛一起样食品各做一盘带到晚会，和其他奶牛一起分享。但考虑到食品太多会浪费掉，他们给每种食品的总盘分享。但考虑到食品太多会浪费掉，他们给每种食品的总盘数都规定了一个不一定相同的上限值。这让他们很伤脑筋，数都规定了一个不一定相同的上限值。这让他们很伤脑筋，究竟应该怎样做，才能让晚会上食品的总盘数尽量的多呢？究竟应该怎样做，才能让晚会上食品的总

19、盘数尽量的多呢？例如：有例如：有4 4头奶牛，每头奶牛最多可以带头奶牛，每头奶牛最多可以带3 3盘食品。一共盘食品。一共有有5 5种食品，它们的数量上限是种食品，它们的数量上限是2 2、2 2、2 2、2 2、3 3。奶牛。奶牛1 1会做会做食品食品1414，奶牛，奶牛2 2会做食品会做食品2525，奶牛，奶牛3 3会做食品会做食品1 1、2 2、4 4，奶牛奶牛4 4会做食品会做食品1313。那么最多可以带。那么最多可以带9 9盘食品到晚会上。盘食品到晚会上。即奶牛即奶牛1 1做食品做食品2424，奶牛，奶牛2 2做食品做食品3535，奶奶，奶奶3 3做食品做食品1 1、2 2，奶牛，奶牛4

20、 4做食品做食品1 1。这样，。这样，4 4种食品各有种食品各有2 2、2 2、2 2、2 2、1 1盘。盘。篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统123412345奶奶牛牛食食品品S3333T22223权权=1边：边：S奶牛奶牛,保证每头奶牛带的食品的最大量。保证每头奶牛带的食品的最大量。边：食品边：食品T,保证每种食品的最大数量。保证每种食品的最大数量。食品的总盘数最大值食品的总盘数最大值=S到到T的最大流的最大流篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统123412345奶奶牛牛食食品品S3333T22223权权=1S到到T的最大流的最大流=9篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统应用 求二分图的最大匹配 利用网络流建模 所有边的容量都是1