下载文档原格式
⽹络流⼊门--最⼤流算法Dicnic算法感谢WHD的⼤⼒⽀持最早知道⽹络流的内容便是最⼤流问题，最⼤流问题很好理解：解释⼀定要通俗!如右图所⽰,有⼀个管道系统,节点{1,2,3,4},有向管道{A,B,C,D,E},即有向图⼀张. [1]是源点,有⽆限的⽔量,[4]是汇点,管道容量如图所⽰.试问[4]点最⼤可接收的⽔的流量?这便是简单的最⼤流问题,显然[4]点的最⼤流量为50死理性派请注意:流量是单位时间内的,总可以了吧!然⽽对于复杂图的最⼤流⽅法是什么呢,有EK,Dinic,SAP,etc.下⾯介绍Dinic算法()Dinic 算法Dinic算法的基本思路:1. 根据残量⽹络计算层次图。
2. 在层次图中使⽤DFS进⾏增⼴直到不存在增⼴路3. 重复以上步骤直到⽆法增⼴引⾃,相当简单是吧…⼩贴⼠:⼀般情况下在Dinic算法中,我们只记录某⼀边的剩余流量.残量⽹络:包含反向弧的有向图,Dinic要循环的,每次修改过的图都是残量⽹络,层次图:分层图,以[从原点到某点的最短距离]分层的图,距离相等的为⼀层,(⽐如上图的分层为{1},{2,4},{3})DFS:这个就不⽤说了吧…增⼴ :在现有流量基础上发现新的路径,扩⼤发现的最⼤流量(注意:增加量不⼀定是这条路径的流量,⽽是新的流量与上次流量之差)增⼴路:在现有流量基础上发现的新路径.(快来找茬,和上⼀条有何不同?)剩余流量:当⼀条边被增⼴之后(即它是增⼴路的⼀部分,或者说增⼴路通过这条边),这条边还能通过的流量.反向弧:我们在Dinic算法中,对于⼀条有向边,我们需要建⽴另⼀条反向边(弧),当正向(输⼊数据)边剩余流量减少I时,反向弧剩余流量增加I Comzyh的较详细解释(流程) :⽤BFS建⽴分层图注意:分层图是以当前图为基础建⽴的,所以要重复建⽴分层图⽤DFS的⽅法寻找⼀条由源点到汇点的路径,获得这条路径的流量I 根据这条路径修改整个图,将所经之处正向边流量减少I,反向边流量增加I,注意I是⾮负数重复步骤2,直到DFS找不到新的路径时,重复步骤1注意(可以⽆视):Dinic(其实其他的好多)算法中寻找到增⼴路后要将反向边增加IDinic中DFS时只在分层图中DFS，意思是说DFS的下⼀个节点的Dis(距源点的距离)要⽐⾃⼰的Dis⼤1,例如在图1中第⼀个次DFS中,1->2->4这条路径是不合法的,因为Dis[2]=1;Dis[4]=1;步骤2中“获得这条路径的流量I “实现:DFS函数有参量low,代表从源点到现在最窄的(剩余流量最⼩)的边的剩余流量,当DFS到汇点是,Low便是我们要的流量I对于反向弧(反向边)的理解:这⼀段不理解也不是不可以,对于会写算法没什么帮助,如果你着急,直接⽆视即可.先举⼀个例⼦(如右图):必须使⽤反向弧的流⽹络在这幅图中我们⾸先要增⼴1->2->4->6,这时可以获得⼀个容量为2的流,但是如果不建⽴4->2反向弧的话,则⽆法进⼀步增⼴,最终答案为2,显然是不对的,然⽽如果建⽴了反向弧4->2,则第⼆次能进⾏1->3->4->2->5->6的增⼴,最⼤流为3.Comzyh对反向弧的理解可以说是”偷梁换柱“,请仔细阅读:在上⾯的例⼦中,我们可以看出,最终结果是1->2->5->6和1->2->4->6和1->3->4->6.当增⼴完1->2->4->5(代号A)后,在增⼴1->3->4->2->5->6(代号B),相当于将经过节点2的A流从中截流1(总共是2)⾛2->5>6,⽽不⾛2->4>6了,同时B 流也从节点4截流出1(总共是1)⾛4->6⽽不是4->2->5->6,相当于AB流做加法.简单的说反向弧为今后提供反悔的机会,让前⾯不⾛这条路⽽⾛别的路.Alwa同学⾮要我给他的⽂章加⼀个链接,⼤家可以看看他的⽂章:。
⽹络流（⼆）最⼤流的增⼴路算法传送门：⽹络流的相关定义：源点：有n个点，有m条有向边，有⼀个点很特殊，只出不进，叫做源点。
汇点：另⼀个点也很特殊，只进不出，叫做汇点。
容量和流量：每条有向边上有两个量，容量和流量，从i到j的容量通常⽤c[i,j]表⽰,流量则通常是f[i,j].通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最⼤的车流量。
很显然的，流量<=容量。
⽽对于每个不是源点和汇点的点来说，可以类⽐的想象成没有存储功能的货物的中转站，所有“进⼊”他们的流量和等于所有从他本⾝“出去”的流量。
最⼤流：把源点⽐作⼯⼚的话，问题就是求从⼯⼚最⼤可以发出多少货物，是不⾄于超过道路的容量限制，也就是，最⼤流。
求解思路：⾸先，假如所有边上的流量都没有超过容量(不⼤于容量)，那么就把这⼀组流量，或者说，这个流，称为⼀个可⾏流。
⼀个最简单的例⼦就是，零流，即所有的流量都是0的流。
(1).我们就从这个零流开始考虑，假如有这么⼀条路，这条路从源点开始⼀直⼀段⼀段的连到了汇点，并且，这条路上的每⼀段都满⾜流量<容量，注意，是严格的<,⽽不是<=。
(2).那么，我们⼀定能找到这条路上的每⼀段的(容量-流量)的值当中的最⼩值delta。
我们把这条路上每⼀段的流量都加上这个delta，⼀定可以保证这个流依然是可⾏流，这是显然的。
(3).这样我们就得到了⼀个更⼤的流，他的流量是之前的流量+delta，⽽这条路就叫做增⼴路。
我们不断地从起点开始寻找增⼴路，每次都对其进⾏增⼴，直到源点和汇点不连通，也就是找不到增⼴路为⽌。
(4).当找不到增⼴路的时候，当前的流量就是最⼤流，这个结论⾮常重要。
补充：(1).寻找增⼴路的时候我们可以简单的从源点开始做BFS，并不断修改这条路上的delta 量，直到找到源点或者找不到增⼴路。
(2).在程序实现的时候，我们通常只是⽤⼀个c 数组来记录容量，⽽不记录流量，当流量+delta 的时候，我们可以通过容量-delta 来实现，以⽅便程序的实现。
⽹络流（最⼤流-Dinic算法）⽹络流定义 在图论中，⽹络流（Network flow）是指在⼀个每条边都有容量（Capacity）的有向图分配流，使⼀条边的流量不会超过它的容量。
通常在运筹学中，有向图称为⽹络。
顶点称为节点（Node）⽽边称为弧（Arc）。
⼀道流必须匹配⼀个结点的进出的流量相同的限制，除⾮这是⼀个源点（Source）──有较多向外的流，或是⼀个汇点（Sink）──有较多向内的流。
⼀个⽹络可以⽤来模拟道路系统的交通量、管中的液体、电路中的电流或类似⼀些东西在⼀个结点的⽹络中游动的任何事物。
————维基百科 最⼤流 正如可以通过将道路交通图模型化为有向图来找到从⼀个城市到另⼀个城市之间的最短路径，我们也可以将⼀个有向图看做是⼀个“流⽹络”并使⽤它来回答关于物料流动⽅⾯的问题。
设想⼀种物料从产⽣它的源结点经过⼀个系统，流向消耗该物料的汇点这样⼀个过程。
源结点以某种稳定的速率⽣成物料，汇点则以同样的速率消耗物料。
从直观上看，物料在系统中任何⼀个点上的“流量”就是物料移动的速率。
这种流⽹络可以⽤来建模很多实际问题，包括液体在管道中的流动、装配线上部件的流动、电⽹中电流的流动和通信⽹络中信息的流动。
我们可以把流⽹络中每条有向边看做是物料的⼀个流通通道。
每条通道有限定的容量，是物料流经该通道时的最⼤速率，如⼀条管道每⼩时可以流过200加仑的液体。
流⽹络中的结点则是通道的连接点。
除了源结点和终结点外，物料在其他结点上只是流过，并不积累或聚集。
换句话说，物料进⼊⼀个结点速率必须与其离开该结点的速率相等。
这个性质称为“流量守恒”，这⾥的流量守恒与Kirchhoff电流定律等价。
在最⼤流问题中，我们希望在不违反任何容量限制的情况下，计算出从源结点运送物料到汇点的最⼤速率。
这是与流⽹络有关的所有问题中最简单的问题之⼀().，这个问题可以由⾼效的算法解决。
⽽且，最⼤流算法中的⼀些基本技巧可以⽤来解决其他⽹络流问题。
网络流--BFS增广求最大流……2009/01/15 21:35【本文只讲了BFS增广求最大流,ps:本文乃原创,转载说明出处啊.】囧，今天上一天课，就把最大流的BFS增广、先流预推法、最大流最小割定理、最小费用流讲完了。
而我，就只记住了BFS增广和最大流最小割定理。
最小费用流ms差不多明白了。
所以先讲讲BFS增广求最大流的算法吧。
简单的来说，就是从S(源)开始BFS，直到到达T(汇)or不存在增广路。
所谓增广路就是从S开始到T的一条路径，而且这条路径上的所有边都是非饱和边，即f(i,j)<c(i,j)。
因为都是非饱和边，所以这条路径上的边还可以增大经过它们的流，所以称为增广路。
而且，这条增广路可以增加的流量，决定于，这条路径上的剩余容量最小的那一条边，可增加的流量就是这最小的剩余流量。
所以说，求最大流的办法就是，不断地寻找增广路，先找到一条增广路，然后把这条路径上的，所有边，减掉，这条增广路可以增大的流，这样重复，直到找不到增广路为止。
下面看看我这段有注释的代码。
#include<iostream>using namespace std;const long N=110;const long maxint=(1<<31)-1;long n,m,s,t,x,y,z;long g[N][N],pre[N],low[N];//g[][]表示原始图，pre[i]表示路径中第i个节点的前一个节点//low[i]表示到达第i个节点时，路径中可增广的流量，//即到第i个节点时，路径上的边剩余容量的最小值。
//low[t]就是整条增广路里的边的剩余容量的最小值，//就是这条路可以增大的流的大小long q[N],head=0,tail=0;// q[]就是队列，我们用BFS来扩展节点，扩展到了T就表示找到了一条增广路long Maxflow=0;// 记录最大流的大小inline void push(long v){//入队q[++tail]=v;}inline long pop(){//出队return q[++head];}inline void clear(){//队列初始化head=tail=0;}int main(){cin>>n>>m>>s>>t;for(long i=1;i<=m;i++){cin>>x>>y>>z;g[x][y]=g[y][x]=z;}while(true){//初始化memset(low,-1,sizeof(low));memset(pre,-1,sizeof(pre));clear();push(s);low[s]=maxint; //源点入队，low[s]赋为无穷大，不可能赋其他小的值啊，自己想想为什么？//开始广搜while(head<tail){long x=pop();for(long i=1;i<=n;i++){if(g[x][i]>0&&pre[i]<0){//g[x][i]>0表示这条边还没满啊，pre[i]<0就表示还没前驱，就是还没被扩展啦push(i); //入队low[i]=min(low[x],g[x][i]); //然后就考虑这条边的剩余容量是不是比前面所找到的所有都小，//是的话就更新呗，不是的话就等于之前的最小的咯。
⽹络流之最⼤流的增⼴路径算法扩展：多路增⼴⼀般的,在执⾏增⼴路算法时,都是先⽤BFS或DFS从源到汇找到⼀条增⼴路,记录下应修改的流量,然后再顺着路倒回去增⼴.反复这个过程直到增⼴路找不到了为⽌.显然的,我们做了很多⽆⽤功,假设有两条很长的增⼴路,前⾯⼤部分都是重叠的,只是在最后关头分了个岔,⽽程序却把前⾯很长的路⾛了两次.为什么要这样?不妨把两条增⼴路合并起来,不⽌是两条,所有的增⼴路都可以按其前缀合并起来,⽽形成⼀棵增⼴树.找增⼴树可以⽤DFS,正如⽣成搜索树⼀样.简⽽⾔之,对于当前的每⼀个结点记录⼀个可提供的最⼤流量,源点的可供流量显然是⽆穷⼤,当推到下⼀个点时,最⼤流量取边的容量和上个点提供的最⼤流量的较⼩值.当到达汇点时,⾃然DFS开始回朔,这时按当前点的已⽤流量增⼴当前点与他⽗亲相连的边,同时将增⼴值累加到他⽗亲的已⽤流量上,并在他⽗亲的可提供流量上减掉这个值,以便在搜索他⽗亲剩下的⼉⼦时,让所有⼉⼦的已⽤流量总和不⼤于⽗亲的可提供流量,不然就出错了.我们按照以下步骤做:search node(available){1.得到node的可提供流量available2.search node's all son(可提供流量){inc(已⽤流量,当前⼉⼦实际增⼴的流量)dec(可提供流量,<同上>)}3.⽤得到的已⽤流量的值增⼴边(node-node's father)4.return 边的增⼴量到 node'fahter}每进⾏⼀次以上步骤,我们就完成了⼀次多路增⼴,并且返回了⼀个值到源点,即DFS的根.这个值表⽰本次操作中将流量扩⼤了多少.重复操作直到返回值为0.得到最⼤流的数值即累加每次的返回值.#include <iostream>#include <queue>#define msize 1024 //最⼤顶点数⽬using namespace std;int d[msize];//标号int r[msize][msize];//残留⽹络，初始为原图int num[msize];//num[i]表⽰标号为i的顶点数有多少int pre[msize];int n,m,s,t;//m个顶点，n条边，从源点s到汇点tvoid ini_d()//BFS计算标号，汇点t标号为0{int k;queue<int>Q;memset(d,1,sizeof(d));memset(num,0,sizeof(num));Q.push(t);d[t]=0;num[0]=1;while(!Q.empty()){k=Q.front(),Q.pop();for(int i=0;i<m;i++){if(d[i]>=m&&r[i][k]>0){d[i]=d[k]+1;Q.push(i);num[d[i]]++;}}}}int findAlowArc(int i)//从i出发寻找允许弧{int j;for(j=0;j<m;j++)if(r[i][j]>0&&d[i]==d[j]+1)return j;return-1;}int reLable(int i)//重新标号{int mm=INT_MAX;for(int j=0;j<m;j++)if(r[i][j]>0) mm=min(mm,d[j]+1);return mm==INT_MAX?m:mm;}int maxFlow(int s,int t)//从源点s出发的最⼤流{int flow=0,i=s,j;int delta;//增量memset(pre,-1,sizeof(pre));while(d[s]<m){j=findAlowArc(i);if(j>=0){pre[j]=i;i=j;if(i==t)//更新残留⽹络{delta=INT_MAX;for(i=t;i!=s;i=pre[i])delta=min(delta,r[pre[i]][i]);for(i=t;i!=s;i=pre[i])r[pre[i]][i]-= delta, r[i][pre[i]]+= delta;flow += delta;}}else{int x=reLable(i);//重新标号num[x]++;num[d[i]]–;if(num[d[i]]==0)return flow;//间隙优化d[i]=x;if(i!=s) i=pre[i];}}return flow;｝FF算法分为三个步骤，⾸先寻找⼀条增⼴路（如果没有增⼴路，则返回最⼤流），同时保存路径；其次，对路径上的流量求最⼩值，记为min；最后根据路径修改⽹络，对于前向边，减去最⼩值，对于后向边，加上最⼩值，或者直接修改容量。
