最大流算法

网络流初步◆最大流算法◆最小费用最大流◆最大流最小割定理最大流算法网络流之一•问题：问从S到T的最大水流量是多少？1S43256t73484246实例：有一自来水管道输送系统，起点是S，目标是T，途中经过的管道都有一个最大的容量。1S43256t7348424646222446最大水流量是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：流入量=整个网络的流量中间点：总流入量=总流出量那么整个网络中的流量成为一个可行流。区分：容量和流量124356423454121243542333112435642345411243542353334一个可行流：5一个可行流：7图1图22、最大流•在所有的可行流中，流量最大的一个流的流量如：图2中可行流7也是最大流。•最大流可能不只一个。二、最大流算法步骤：（1）如果存在增广路径,就找出一条增广路径（2）然后沿该条增广路径进行更新流量（增加流量）◆Ford-Fulkerson（福特-福克森）算法：1、增广路径•从s到t的一条简单路径，若边(u,v)的方向与该路径的方向一致，称(u,v)为正向边，方向不一致时称为逆向边。简单路：13245中。（1，3）（2，4）（4，5）是正向边。（3，2）是逆向边。1243564234512435642345若路径上所有的边满足：①所有正向边有：f(u,v)c(u,v)②所有逆向边有：f(u,v)0则称该路径为一条增广路径(可增加流量)增广路径：两条增广路径：135132451243564234522212435642345222增加流量=？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;增广后，总流量增加了d12435642345样例：开始流量为:sum=01、一条增广路径:1235d=min{4,2,4}=2增加流量:2Sum=212435642345222124356423452、一条增广路径:1245d=min{4-2,3,5}=2增加流量:2Sum=2+2=412435642345222124356423452221243564234522212435642345222124356423452221243564234522-1=1212435423452223、一条增广路径:1３245d=min{6,2,3-2,5-2}=1增加流量:1Sum=4+1=51112-3减少１，加到２-４２-3减的１由１-３补充１4、一条增广路径:1３5d=min{6-1,4-2}=2增加流量:2Sum=5+2=71243564234522-1=121243542342221111243564234522-1=12124354234522211122•定理：可行流f为最大流，当且仅当不存在关于f的增广路径证：若f是最大流，但图中存在关于f的增广路径，则可以沿该增广路径增广，得到的是一个更大的流，与f是最大流矛盾。所以，最大流不存在增广路径。◆Ford-Fulkerson方法(增广流)求最大流（福特-福克森）步骤：（1）如果存在增广路径,就找出一条增广路径DFS,BFS（2）然后沿该条增广路径进行更新流量（增加流量）While有增广路径do更新该路径的流量迭代算法c[u,v]：容量f[u,v]：流量B[i]：保存找到的增广路径，记录路径上结点i的前驱结点。Sum：最大流量。假定：1是源点S；n是汇点T。算法的实现：functionfindflow(k:integer):boolean;{找结点k的后继结点i}vari:integer;beginifk=nthenexit(true);{找到了一条增广路径}fori:=1tondoif(b[i]=-1)and((c[k,i]-f[k,i]0)or(f[i,k]0))thenbeginb[i]:=k;iffindflow(i)thenexit(true);end;exit(false);end;1）：DFS找增广路径2）procedureaddflow;//沿增广路径增广（增加流量）d:=maxint;{增量}i:=n;{沿增广路径的终点向起点反向求d}whileb[i]0dobeginifc[b[i],i]0thend:=min(d,c[b[i],i]-f[b[i],i]);{正向边}ifc[i,b[i]]0thend:=min(d,f[i,b[i]]);{逆向边}i:=b[i];end;i:=n;whileb[i]0do{逆向更新每条边的流量}beginifc[b[i],i]0theninc(f[b[i],i],d);{正向边}ifc[i,b[i]]0thendec(f[i,b[i]],d);{逆向边}i:=b[i];end;inc(sum,d);{总流量增加d}主程序：fori:=1tondob[i]:=-1;{初始化增广路径}b[1]:=0;whilefindflow(1)do{增广流}beginaddflow;fori:=1tondob[i]:=-1;b[1]:=0;end;writeln(sum);{输出最大流}fori:=1tondo{输出每条边的流量}forj:=1tondoiff[i,j]0thenwriteln(i,'--',j,'',f[i,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)。增广路上正向边流量增加，逆向边增加流量减少。1243564234522212435642345222d(u,v)=c(u,v)d(v,u)=0深搜找增广路径过程functionfind(k:integer):boolean;ifk=nthenexit(true);fori:=1tondoif(b[i]=-1)and(d[k,i]0)then[b[i]:=k;iffind(i)thenexit(true);//此处b[i]不需要变回-1]exit(false);//b[1]=0;b[2~n]=-1;主函数中调用find(1)广搜找增广路径过程functionbfsbfs:boolean;a是广搜队列fori:=1tondob[i]:=-1;b是前驱b[1]:=0;a[1]:=1;open:=0;closed:=1;whileopencloseddo[inc(open);k:=a[open];fori:=1tondod是残余流量if(b[i]=-1)and(d[k,i]0)then[inc(closed);a[closed]:=i;b[i]:=k;ifi=nthenexit(true);找到增广路]]exit(false);没找到增广路增广过程min:=maxint;i:=n;whileb[i]0(i1)do//逆向求增加流min[ifmind[b[i],i]thenmin:=d[b[i],i];i:=b[i];]i:=n;whileb[i]0(i1)do////逆向修改流量[dec(d[b[i],i],min);inc(d[i,b[i]],min);i:=b[i];]inc(sum,min);sum是总流量问题1：奶牛的新年晚会奶牛们要举办一次别开生面的新年晚会。每头奶牛会做一些不同样式的食品（单位是盘）。到时候他们会把自己最拿手的不超过k样食品各做一盘带到晚会，和其他奶牛一起分享。但考虑到食品太多会浪费掉，他们给每种食品的总盘数都规定了一个不一定相同的上限值。这让他们很伤脑筋，究竟应该怎样做，才能让晚会上食品的总盘数尽量的多呢？例如：有4头奶牛，每头奶牛最多可以带3盘食品。一共有5种食品，它们的数量上限是2、2、2、2、3。奶牛1会做食品1…4，奶牛2会做食品2…5，奶牛3会做食品1、2、4，奶牛4会做食品1…3。那么最多可以带9盘食品到晚会上。即奶牛1做食品2…4，奶牛2做食品3…5，奶奶3做食品1、2，奶牛4做食品1。这样，4种食品各有2、2、2、2、1盘。123412345奶牛食品S3333T22223权=1边：S奶牛,保证每头奶牛带的食品的最大量。边：食品T,保证每种食品的最大数量。食品的总盘数最大值=S到T的最大流123412345奶牛食品S3333T22223权=1S到T的最大流=9应用•求二分图的最大匹配•利用网络流建模•所有边的容量都是1