您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
国家集训队论文集王欣上《浅谈基于分.doc 26页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：280 &&
你可能关注的文档：
··········
浅谈基于分层思想的网络流算法上海市延安中学王欣上[关键字]层次图网络流基本算法应用MPLADinicMPM[摘要]本文详细地介绍了基于层次图概念的三种算法，并通过例题来说明Dinic算法在信息学竞赛中的优越性。[目录]一、引言 3二、预备概念 32.1剩余图的概念 32.2顶点的层次 42.3层次图的概念 42.4阻塞流的概念 5三、最短路径增值算法(MPLA)的步骤及复杂度分析 53.1算法步骤 53.2定理的证明 63.3复杂度分析 8四、Dinic算法的步骤以及复杂度分析 94.1算法步骤 94.2复杂度分析 13五、Dinic算法在信息学竞赛中的应用 15例题1最大获利(profit) 15例题2矩阵游戏 18六、MPM的算法步骤以及复杂度分析 196.1算法步骤 196.2复杂度分析 20七、总结 21[正文]引言图论这门古老而又年轻的学科在信息学竞赛中占据了相当大的比重。其中，网络流算法经常在题目中出现。网络流涵盖的知识非常丰富，从基本的最小割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等，同学们在平时需要多多涉猎这方面的知识，不断积累，才能应对题目的各种变化。随着信息学竞赛的不断发展，其题目的难度以及考察范围都不断增大。现在，对于一些新出现的题目，仅仅掌握最朴素的网络流算法并不足以解决问题。本文针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的3个网络流算法，并通过列举和比较说明了其在解题中的应用，而对一些基础的知识，如最小割最大流定理等，没有作具体阐释，大家可以在许多其他网络流资料中找到。二、预备概念2.1剩余图的概念给定一个流量网络、源点、汇点、容量函数，以及其上的流量函数。我们这样定义对应的剩余图：剩余图中的点集与流量网络中的点集相同，即。对于流量网络中的任一条边，若，那么边，这条边在剩余图中的权值为；同时，若那么边，这条边在剩余图中的权值为。我们可以发现，流量网络中的每条边在剩余图中都化作一条或二条边。剩余图中的每条边都表示在原流量网络中能沿其方向增广。剩余图的权值函数表示在流量网络中能够沿着的方向增广大小为的流量。所以在剩余图中，从源点到汇点的任意一条简单路径都对应着一条增广路，路径上每条边的权值的最小值即为能够一次增广的最大流量。2.2顶点的层次在剩余图中，我们把从源点到点的最短路径长度称作点的层次，记为。源点的层次为0。在下面这张剩余图中：每个点旁边的数字即表示该点在图中的层次。2.3层次图的概念我们这样定义层次图：对于剩余图中的一条边，当且仅当时，边；直观地讲，层次图是建立在剩余图基础之上的一张“最短路图”。从源点开始，在层次图中沿着边不管怎么走，经过的路径一定是终点在剩余图中的最短路。2.4阻塞流的概念在流量网络中存在一可行流，当该网络的层次图中不存在增广路时，我们称流函数为层次图的阻塞流。三、最短路径增值算法(MPLA)的步骤及复杂度分析3.1算法步骤1、初始化流量，计算出剩余图2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束3、在层次图内不断用bfs增广，直到层次图内没有增广路为止4、转步骤2
之前我们讲到的层次图将被应用在最短路径增值算法中。首先，我们看一下最短路径增值算法的步骤：算法中，2、3步被循环执行，我们将执行2、3步的一次循环称为一个阶段。每个阶段中，我们首先根据剩余图建立层次图，然后不断用bfs在层次图内增广，寻找阻塞流。增广完毕后，进入下一个阶段。这样不断重复，直到汇点不在层次图内出现为止。汇点不在层次图内意味着在剩余图中不存在一条从源点到汇点的路径，即没有增广路。在程序实现的时候，层次图并不用被“建”出来，我们只需对每个顶点标记层次，增广的时候，判断边是否满足这一约束即可。3.2定理的证明定理：对于有n个点的流量网络，在最短路径增值算法中，最多有n个阶段。也就是说，在算法中层次图最多被建立n次。证明这个定理有助于我们进行算法复杂度分析。证明：在建立完层次图以后，假设从源点到汇点的最短路径长度为k，我们将层次图中所有的点分到k+1个集合中，第i个集合为，如下图所示：在剩余图中，存在着2类边。第一类：从第个集合中的顶点连到第个集合中的顶点第二类：从第个集合中的顶点连到第个集合中的顶点在层次图中，只存在第一类边，这是由层次图的性质决定的。我们所要找的增广路中的边也必定是第一类边。当我们对一条增广路径增广后，会删除一条或多条增广路中的饱和边，也就是第一类边；而同时会在剩余图中加入一些与增广路径中的边反向的边。这些新加入的边一定是第二类边。如下图所示，在剩余图(a)中，找到一条从左向右的增广路径，能够增广的流量大小为2。增广后的结果是剩余图(b)。可以发现，在剩余图(a)里面，中间一条红色第一类边在增广后饱和而被删除了，同时，在剩余图(b)中，新增了2
正在加载中，请稍后...7668人阅读
数据结构（202）
算法（604）
&1432人阅读&&&
&&&&&&&在算法导论中对求解最大流问题给出了一般性的解决方法，但并没有涉及到具体的实现。在这里我还是重新的对求解最大流的思想进行一般性的描述，然后再给出具体的实现。
&&&&&&Ford-Fulkerson方法依赖于三种重要思想，这三个思想就是在上一篇中提到的：残留网络，增广路径和割。Ford-Fulkerson方法是一种迭代的方法。开始时，对所有的u，v∈V有f(u,v)=0，即初始状态时流的值为0。在每次迭代中，可通过寻找一条“增广路径”来增加流值。增广路径可以看成是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直至增广路径都被找出来，根据最大流最小割定理，当不包含增广路径时，f是G中的一个最大流。在算法导论中给出的Ford-Fulkerson实现代码如下：
&&&& FORD_FULKERSON(G,s,t)
&&&& 1&& for each edge(u,v)∈E[G]
&&&&&2&&&&&&&&do f[u,v] &— 0
&&&& 3&&&&&&&&&&&&f[v,u] &— 0
&&&& 4&& while there exists a path p from s to t in the residual network Gf
&&&& 5&&&&&&& do cf(p) &— min{ cf(u,v) : (u,v) is in p }
&&&& 6&&&&&&& for each edge(u,v) in p
&&&&&7&&&&&&&&&&&&&do f[u,v] &— f[u,v]+cf(p)&&&&&&&&&//对于在增广路径上的正向的边，加上增加的流
&&&&&8&&&&&&&&&&&&&&&&& f[v,u] &— -f[u,v]&&&&&&&&&&&&&&&&//对于反向的边，根据反对称性求
&&&& 第1~3行初始化各条边的流为0，第4~8就是不断在残留网络Gf中寻找增广路径，并沿着增广路径的方向更新流的值，直到找不到增广路径为止。而最后的最大流也就是每次增加的流值cf(p)之和。在实际的实现过程中，我们可以对上述代码做些调整来达到更好的效果。如果我们采用上面的方法，我们就要保存两个数组，一个是每条边的容量数组c，一个就是上面的每条边的流值数组f，在增广路径中判断顶点u到v是否相同时我们必须判断c[u][v]-f[u][v]是否大于0，但是因为在寻找增广路径时是对残留网络进行查找，所以我们可以只保存一个数组c来表示残留网络的每条边的容量就可以了，这样我们在2~3行的初始化时，初始化每条边的残留网络的容量为G的每条边的容量（因为每条边的初始流值为0）。而更新时，改变7~8行的操作，对于在残留网络上的边(u,v)执行c[u][v]-=cf(p)，而对其反向的边(v,u)执行c[v][u]+=cf(p)即可。
&&&&& 现在剩下的最关键问题就是如何寻找增广路径。而Ford-Fulkerson方法的运行时间也取决于如何确定第4行中的增广路径。如果选择的方法不好，就有可能每次增加的流非常少，而算法运行时间非常长，甚至无法终止。对增广路径的寻找方法的不同形成了求最大流的不同算法，这也是Ford-Fulkerson被称之为“方法”而不是“算法”的原因。下面将给出Ford-Fulkerson方法的具体实现细节：
int c[MAX][MAX];&&//残留网络容量
int pre[MAX];&&//保存增广路径上的点的前驱顶点
bool visit[MAX];
int Ford_Fulkerson(int src,int des,int n){&&&//src：源点 des：汇点 n：顶点个数
&&&& int i,_min,total=0;
&&&& while(true){
&&&&&&&& if(!Augmenting_Path(src,des,n))&//如果找不到增广路就返回，在具体实现时替换函数名
&&&&&&&& _min=(1&&30);
&&&&&&&& i=
&&&&&&&& while(i!=src){&&&//通过pre数组查找增广路径上的边，求出残留容量的最小值
&&&&&&&&&&&& if(_min&c[pre[i]][i])_min=c[pre[i]][i];
&&&&&&&&&&&& i=pre[i];
&&&&&&&& }
&&&&&&&& i=
&&&&&& & while(i!=src){&&&&//再次遍历，更新增广路径上边的流值
&&&&&&&&&&&& c[pre[i]][i]-=_
&&&&&&&&&&&& c[i][pre[i]]+=_
&&&&&&&&&&&& i=pre[i];
&&&&&&&& }
&&&&&&&& total+=_&&&&&//每次加上更新的值
Edmonds-Karp算法实际上就是采用广度优先搜索来实现对增广路径的p的计算，代码如下：
bool Edmonds_Karp(int src,int des,int n){
&&&& int v,i;
&&&& for(i=0;i&n;i++)visit[i]=
&&&&&front=rear=0;&&&&&//初始化
&&&& que[rear++]=
&&&& visit[src]=
&&& &while(front!=rear){&&&&&//将源点进队后开始广搜的操作
&&&&&&&& v=que[front++];&
&&&&&&&&&//这里如果采用邻接表的链表实现会有更好的效率，但是要注意(u,v)或(v,u)有任何一条
&&&&&&&& //边存在于原网络流中，那么邻接表中既要包含(u,v)也要包含(v,u)
&&&&&&&& for(i=0;i&n;i++){&
&&&&&&&&&&&& if(!visit[i]&&c[v][i]){&&//只有残留容量大于0时才存在边
&&&&&&&&&&&&&&&& que[rear++]=i;
&&&&&&&&&&&&&&&& visit[i]=
&&&&&&&&&&&&&&&&&pre[i]=v;
&&&&&&&&&&&&&&&& if(i==des)&&&//如果已经到达汇点，说明存在增广路径返回true
&&&&&&&&&&&& }
&&&&&&&& }
分类：&&628人阅读&&&
/*****以下来自&&浅谈基于分层思想的网络流算法&& 王欣*****/
短路增值算法(MPLA)
汇点不在层次图内意味着在剩余图中不存在一条从源点到汇点的路径，即没有增广路。
在程序实现的时候，层次图并不用被“建”出来，我们只需对每个顶点标记层次，增广的时候，判断边是否满足level(u) +1= level(v)这一约束即可。
最大流模板【EdmondsKarp算法，简称EK算法，O(m^2n)】
&&&因为是初学教程，所以我会尽量避免繁杂的数学公式和证明。也尽量给出了较为完整的代码。
本文的目标群体是网络流的初学者，尤其是看了各种NB的教程也没看懂怎么求最大流的小盆友们。本文的目的是，解释基本的网络流模型，最基础的最大流求法，即bfs找增广路法，也就是EK法，全名是Edmond-Karp，其实我倒是觉得记一下算法的全名和来历可以不时的拿出来装一装。
&&&&比如说这个，EK算法首先由俄罗斯科学家Dinic在1970年提出，没错，就是dinic算法的创始人，实际上他提出的也正是dinic算法，在EK的基础上加入了层次优化，这个我们以后再说，1972年Jack Edmonds和Richard Karp发表了没有层次优化的EK算法。但实际上他们是比1790年更早的时候就独立弄出来了。
&&&&你看，研究一下历史也是很有趣的。
&&&&扯远了，首先来看一下基本的网络流最大流模型。
&&&&有n个点，有m条有向边，有一个点很特殊，只出不进，叫做源点，通常规定为1号点。另一个点也很特殊，只进不出，叫做汇点，通常规定为n号点。每条有向边上有两个量，容量和流量，从i到j的容量通常用c[I,j]表示,流量则通常是f[I,j]。通常可以把这些边想象成道路，流量就是这条道路的车流量，容量就是道路可承受的最大的车流量。很显然的，流量&=容量。而对于每个不是源点和汇点的点来说，可以类比的想象成没有存储功能的货物的中转站，所有”进入”他们的流量和等于所有从他本身”出去”的流量。
&&&&把源点比作工厂的话，问题就是求从工厂最大可以发出多少货物，是不至于超过道路的容量限制，也就是，最大流。
&&&&比如这个图。每条边旁边的数字表示它的容量。
&&&&下面我们来考虑如何求最大流。
&&&&首先，假如所有边上的流量都没有超过容量(不大于容量)，那么就把这一组流量，或者说，这个流，称为一个可行流。一个最简单的例子就是，零流，即所有的流量都是0的流。
我们就从这个零流开始考虑，假如有这么一条路，这条路从源点开始一直一段一段的连到了汇点，并且，这条路上的每一段都满足流量&容量，注意，是严格的&,而不是&=。那么，我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta，一定可以保证这个流依然是可行流，这是显然的。
&&&&这样我们就得到了一个更大的流，他的流量是之前的流量+delta，而这条路就叫做增广路。
&&&&我们不断地从起点开始寻找增广路，每次都对其进行增广，直到源点和汇点不连通，也就是找不到增广路为止。当找不到增广路的时候，当前的流量就是最大流，这个结论非常重要。
寻找增广路的时候我们可以简单的从源点开始做bfs，并不断修改这条路上的delta量，直到找到源点或者找不到增广路。
这里要先补充一点，在程序实现的时候，我们通常只是用一个c数组来记录容量，而不记录流量，当流量+1的时候，我们可以通过容量-1来实现，以方便程序的实现。
Bfs过程的半伪代码：下面另给一个C++版的模板
&&&&int i,j,k,v,u;
&&&&memset(pre,-1,sizeof(pre));
&&&&for(i=1;i&=n;++i)flow[i]=max_
&&&&queue&int&
&&&&pre[start]=0;
&&&&que.push(start);
&&&&while(!que.empty())
&&&&&&&&v=que.front();
&&&&&&&&que.pop();
&&&&&&&&for(i=1;i&=n;++i)
&&&&&&&&&&&&u=i;
&&&&&&&&&&&&if(u==start||pre[u]!=-1||map[v][u]==0)
&&&&&&&&&&&&pre[u]=v;
&&&&&&&&&&&&flow[u]=MIN(flow[v],map[v][u]);
&&&&&&&&&&&&que.push(u);
&&&&if(flow[end]==max_int)return -1;
&&&&return flow[end];
但事实上并没有这么简单，上面所说的增广路还不完整，比如说下面这个网络流模型。
我们第一次找到了1-2-3-4这条增广路，这条路上的delta值显然是1。于是我们修改后得到了下面这个流。（图中的数字是容量）
这时候(1,2)和(3,4)边上的流量都等于容量了，我们再也找不到其他的增广路了，当前的流量是1。
但这个答案明显不是最大流，因为我们可以同时走1-2-4和1-3-4，这样可以得到流量为2的流。
那么我们刚刚的算法问题在哪里呢？问题就在于我们没有给程序一个”后悔”的机会，应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢？回溯搜索吗？那么我们的效率就上升到指数级了。
而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i)，反向边也同样有它的容量。
我们直接来看它是如何解决的：
在第一次找到增广路之后，在把路上每一段的容量减少delta的同时，也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时，inc(c[y,x],delta)
我们来看刚才的例子，在找到1-2-3-4这条增广路之后，把容量修改成如下
这时再找增广路的时候，就会找到1-3-2-4这条可增广量，即delta值为1的可增广路。将这条路增广之后，得到了最大流2。
那么，这么做为什么会是对的呢？我来通俗的解释一下吧。
事实上，当我们第二次的增广路走3-2这条反向边的时候，就相当于把2-3这条正向边已经是用了的流量给”退”了回去，不走2-3这条路，而改走从2点出发的其他的路也就是2-4。（有人问如果这里没有2-4怎么办，这时假如没有2-4这条路的话，最终这条增广路也不会存在，因为他根本不能走到汇点）同时本来在3-4上的流量由1-3-4这条路来”接管”。而最终2-3这条路正向流量1，反向流量1，等于没有流量。
这就是这个算法的精华部分，利用反向边，使程序有了一个后悔和改正的机会。而这个算法和我刚才给出的代码相比只多了一句话而已。
#include&iostream&
#include&queue&
const int maxn=205;
const int inf=0x7
int r[maxn][maxn]; //残留网络，初始化为原图
bool visit[maxn];
int pre[maxn];
bool bfs(int s,int t)&&//寻找一条从s到t的增广路，若找到返回true
&&&&queue&int &
&&&&memset(pre,-1,sizeof(pre));
&&&&memset(visit,false,sizeof(visit));
&&&&pre[s]=s;
&&&&visit[s]=
&&&&q.push(s);
&&&&while(!q.empty())
&&&&&&&&p=q.front();
&&&&&&&&q.pop();
&&&&&&&&for(int i=1;i&=n;i++)
&&&&&&&&&&&&if(r[p][i]&0&&!visit[i])
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&pre[i]=p;
&&&&&&&&&&&&&&&&visit[i]=
&&&&&&&&&&&&&&&&if(i==t)
&&&&&&&&&&&&&&&&q.push(i);
&&&&&&&&&&&&}
int EdmondsKarp(int s,int t)
&&&int flow=0,d,i;
&&&while(bfs(s,t))
&&&&&&&for(i=t;i!=s;i=pre[i])
&&&&&&&&&&&d=d&r[pre[i]][i]? d:r[pre[i]][i];
&&&&&&&for(i=t;i!=s;i=pre[i])
&&&&&&&&&&&r[pre[i]][i]-=d;
&&&&&&&&&&&r[i][pre[i]]+=d;
&&&&&&&flow+=d;
int main()
&&&&while(scanf(&%d%d&,&m,&n)!=EOF)
&&&&&&&&int u,v,w;
&&&&&&&&memset(r,0,sizeof(r));///
&&&&&&&&for(int i=0;i&m;i++)
&&&&&&&&&&&&scanf(&%d%d%d&,&u,&v,&w);
&&&&&&&&&&&&r[u][v]+=w;
&&&&&&&&printf(&%d\n&,EdmondsKarp(1,n));
&&&&return 0;
Dinic算法的思想也是分阶段地在层次图中增广。
它与最短路径增值算法不同之处是：在Dinic算法中，我们用一个dfs过程代替多次bfs来寻找阻塞流。下面给出其算法步骤：
增广过程图解
伪代码描述
在程序里，p表示找到的增广路径，p.top为路径中的最后一个顶点。一开始，p中只有源点。
整个While循环分为2个操作。如果p的最后一个顶点为汇点，也就是说找到了增广路，那么对p增广，注意到增广后一定有一条或多条p中的边被删除了。这时，我们使增广路径后退至p中从源点可到达的最后一个顶点。
如果p的最后一个顶点不为汇点，那么观察最后那个的顶点u 。若在层次图中存在从u连出的一条边，比如(u,v)，我们就将顶点v放入路径p中，继续dfs遍历；否则，点u对之后的dfs遍历就没有用了，我们将点u以及层次图中连到u的所有边删除，并且在p中后退一个点。
Dfs过程将会不断重复这2个操作，直到从源点连出的边全部被删除为止。
/*****以上来自&&浅谈基于分层思想的网络流算法&& 王欣*****/
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：3617974次
积分：33605
积分：33605
排名：第115名
原创：22篇
转载：1920篇
评论：464条
(37)(14)(28)(148)(78)(74)(36)(80)(90)(42)(139)(241)(117)(357)(181)(63)(56)(57)(5)(47)(1)(30)(23)发布时间： 12:30:06
编辑：www.fx114.net
本篇文章主要介绍了"Dinic算法"，主要涉及到Dinic算法方面的内容，对于Dinic算法感兴趣的同学可以参考一下。
图论这门古老而又年轻的学科在信息学竞赛中占据了相当大的比重。其中，网络流算法经常在题目中出现。网络流涵盖的知识非常丰富，从基本的最小割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等，同学们在平时需要多多涉猎这方面的知识，不断积累，才能应对题目的各种变化。
随着信息学竞赛的不断发展，其题目的难度以及考察范围都不断增大。现在，对于一些新出现的题目，仅仅掌握最朴素的网络流算法并不足以解决问题。本文针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的3个网络流算法，并通过列举和比较说明了其在解题中的应用，而对一些基础的知识，如最小割最大流定理等，没有作具体阐释，大家可以在许多其他网络流资料中找到。
剩余图的概念
给定一个流量网络、源点、汇点、容量函数，以及其上的流量函数。我们这样定义对应的剩余图：剩余图中的点集与流量网络中的点集相同，即。对于流量网络中的任一条边，若，那么边，这条边在剩余图中的权值为；同时，若那么边，这条边在剩余图中的权值为。
我们可以发现，流量网络中的每条边在剩余图中都化作一条或二条边。剩余图中的每条边都表示在原流量网络中能沿其方向增广。剩余图的权值函数表示在流量网络中能够沿着的方向增广大小为的流量。所以在剩余图中，从源点到汇点的任意一条简单路径都对应着一条增广路，路径上每条边的权值的最小值即为能够一次增广的最大流量。
顶点的层次
在剩余图中，我们把从源点到点的最短路径长度称作点的层次，记为。源点的层次为0。在下面这张剩余图中：
每个点旁边的数字即表示该点在图中的层次。
层次图的概念
&&& 我们这样定义层次图：对于剩余图中的一条边，当且仅当时，边；
直观地讲，层次图是建立在剩余图基础之上的一张“最短路图”。从源点开始，在层次图中沿着边不管怎么走，经过的路径一定是终点在剩余图中的最短路。
阻塞流的概念
在流量网络中存在一可行流，当该网络的层次图中不存在增广路时，我们称流函数为层次图的阻塞流。
的步骤及复杂度分析
1、初始化流量，计算出剩余图
2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束
3、在层次图内不断用bfs增广，直到层次图内没有增广路为止
4、转步骤2
之前我们讲到的层次图将被应用在最短路径增值算法中。首先，我们看一下最短路径增值算法的步骤：
算法中，2、3步被循环执行，我们将执行2、3步的一次循环称为一个阶段。每个阶段中，我们首先根据剩余图建立层次图，然后不断用bfs在层次图内增广，寻找阻塞流。增广完毕后，进入下一个阶段。这样不断重复，直到汇点不在层次图内出现为止。汇点不在层次图内意味着在剩余图中不存在一条从源点到汇点的路径，即没有增广路。
在程序实现的时候，层次图并不用被“建”出来，我们只需对每个顶点标记层次，增广的时候，判断边是否满足这一约束即可。
定理的证明
定理：对于有n个点的流量网络，在最短路径增值算法中，最多有n个阶段。
也就是说，在算法中层次图最多被建立n次。证明这个定理有助于我们进行算法复杂度分析。
在建立完层次图以后，假设从源点到汇点的最短路径长度为k，我们将层次图中所有的点分到k+1个集合中，第i个集合为，如下图所示：
在剩余图中，存在着2类边。
第一类：从第个集合中的顶点连到第个集合中的顶点
第二类：从第个集合中的顶点连到第个集合中的顶点
在层次图中，只存在第一类边，这是由层次图的性质决定的。我们所要找的增广路中的边也必定是第一类边。
当我们对一条增广路径增广后，会删除一条或多条增广路中的饱和边，也就是第一类边；而同时会在剩余图中加入一些与增广路径中的边反向的边。这些新加入的边一定是第二类边。如下图所示，在剩余图(a)中，找到一条从左向右的增广路径，能够增广的流量大小为2。增广后的结果是剩余图(b)。可以发现，在剩余图(a)里面，中间一条红色第一类边在增广后饱和而被删除了，同时，在剩余图(b)中，新增了2条绿色的第二类边。
当我们在层次图中找到阻塞流之后，层次图中就不存在从第一个集合一步一步往下走，最后达到第k+1个集合的长为k的路径了。而此时不在层次图中的边都是第二类边。我们可以发现，这个时候在剩余图中的最短路径一定是这样：从源点开始，往下一步一步走，走到某个集合后沿着第二类边向上退至某个集合，再继续一步一步向下走，到某个集合又向上退…………直到走到汇点。
因为必然会经过第二类边，而经过的第一类边的数量&=k，所以路径总长度一定大于k。这即是下一个阶段的最短路径长度。
由此，我们得出了一个结论：
结论：层次图中增广路径长度随阶段而严格递增。
因为增广路径长度最短是1，最长是n-1 ，再算上汇点不在层次图内的最后一次，层次图最多被建造n次，所以最短路径增值算法最多有n个阶段。
复杂度分析
3.3.1建造层次图的复杂度分析
我们将复杂度分析分为建层次图和找增广路两部分讨论。
前面已经证明了，在最短路径增值算法中，最多建n个层次图，每个层次图用bfs一次遍历即可得到。一次bfs遍历的复杂度为，所以建层次图的总复杂度为。
3.3.2增广复杂度分析
我们首先分析在每一阶段中找增广路的复杂度。
注意到每增广一次，层次图中必定有一条边会被删除。层次图中最多有m条边，所以可以认为最多增广m次。在最短路径增广中，我们用bfs来增广。一次增广的复杂度为。其中为bfs的花费，为修改流量的花费。
所以在每一阶段的复杂度为
这样，得到找增广路总的复杂度为
最短路径增值算法的总复杂度即为建层次图的总复杂度与找增广路的总复杂度之和，为。
算法的步骤以及复杂度分析
Dinic算法的思想也是分阶段地在层次图中增广。它与最短路径增值算法不同之处是：在Dinic算法中，我们用一个dfs过程代替多次bfs来寻找阻塞流。下面给出其算法步骤：
1、初始化流量，计算出剩余图
2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束
3、在层次图内用一次dfs过程增广
4、转步骤2
在Dinic的算法步骤中，只有第三步与最短路径增值算法不同。之后我们会发现，dfs过程将会使算法的效率较之MPLA有非常大的提高。
下面是dfs的过程：
While outdegree(s)&0
&&& if u&&t
&&&&&&& if outdegree(u)&0
&&&&&&&&&&& 设(u,v)为层次图中的一条边;
&&&&&&&&&&& pssp,v;&&
&&&&&&& else
&&&&&&&&&&& 从p和层次图中删除点u,
&&&&&&&&&&& 以及和u连接的所有边;
&&&&&&& 增广p（删除了p中的饱和边）;
&&&&&&& 令p.top为p中从s可到达的最后顶点;
在程序里，p表示找到的增广路径，p.top为路径中的最后一个顶点。一开始，p中只有源点。
整个While循环分为2个操作。如果p的最后一个顶点为汇点，也就是说找到了增广路，那么对p增广，注意到增广后一定有一条或多条p中的边被删除了。这时，我们使增广路径后退至p中从源点可到达的最后一个顶点。
如果p的最后一个顶点不为汇点，那么观察最后那个的顶点u 。若在层次图中存在从u连出的一条边，比如(u,v)，我们就将顶点v放入路径p中，继续dfs遍历；否则，点u对之后的dfs遍历就没有用了，我们将点u以及层次图中连到u的所有边删除，并且在p中后退一个点。
Dfs过程将会不断重复这2个操作，直到从源点连出的边全部被删除为止。
下面给出一个dfs的图例，图中，红边代表找到的增广路p中的边。
复杂度分析
和在最短路径增值算法中的证明一样，Dinic算法最多被分为n个阶段。
这样首先可以得到Dinic算法中建立层次图的总复杂度仍是。
我们再来分析dfs过程的总复杂度。在每一阶段，将dfs分成2部分分析：
While outdegree(s)&0
&&& if u&&t
&&&&&&& if outdegree(u)&0
&&&&&&&&&&& 设(u,v)为层次图中的一条边;
&&&&&&&&&&& pssp,v;&&
&&&&&&& else
&&&&&&&&&&& 从p和层次图中删除点u,
&&&&&&&&&&& 以及和u连接的所有边;
&&&&&&& 增广p（删除了p中的饱和边）;
&&&&&&& 令p.top为p中从s可到达的最后顶点;
（1）&&&修改增广路的流量并后退的花费：（即为代码中红框对应的部分）
&&& 在3.3.2小节中我们讲到过，在每一阶段，最多增广m次，每次修改流量的费用为。而一次增广后在增广路中后退的费用也为。所以在每一阶段，修改增广路以及后退的复杂度为。
（2）&&&Dfs遍历时的前进与后退：（即为代码中篮框对应的部分）
&&& 我们将用到3.1小节中的知识。
&&& 在dfs遍历时，如果当前路径的最后一个顶点能够继续扩展，则一定是沿着第一类边向汇点前进了一步。因为增广路径长度最长为n，所以最多连续前进n步后就会遇到汇点。在前进的过程中，可能会遇到没有边能够沿着继续前进的情况，这时，我们将路径中的最后一个点在层次图中删除并出栈。
&&& 注意到每后退一次必定会删除一个点，所以后退的次数最多为n次。在每一阶段中，后退的复杂度为。
&&& 假设在最坏情况下，所有的点最后均被删除，一共后退了n次，这也就意味着，有n次的前进被“无情”地退了回来，这n次前进操作都打了水漂。除去这n次前进和n次后退，其余的前进都对最后找到增广路作了贡献。增广路最多找m次，每次最多前进n个点。所以所有前进操作最多为次，复杂度为。
&&& 于是我们得到：在每一阶段中，dfs遍历时前进与后退的花费为。
综合以上二点，一次dfs的复杂度为。因为最多进行n次dfs，所以在Dinic算法中找增广路的总复杂度为，这也是Dinic算法的总复杂度。
图论这门学科的诞生始于18世纪欧拉证明了七桥问题，发表《依据几何位置的解题方法》一文。但图论的真正发展是从20世纪五六十年代开始的。所以说，图论是一门既古老又年轻的学科。
本文对一些基本的理论，如最大流最小割定理等，不做阐述，读者可以参阅相关网络流资料。
本文中所有涉及到的边若无指明均为有向边。
简单路径：路径中不存在重复的顶点或边
这里指的dfs遍历时的后退操作不是修改流量后进行的后退操作
Dfs遍历是基于栈这一数据结构的
本文标题：
本页链接：