文档介绍：薆莅螀浅谈基于分层思想的网络流算法薈上海市延安中学王欣上芆膂膃肇[关键字]肆层次图网络流基本算法应用芄MPLADinicMPM芁蒇螇芅荿[摘要]膀本文详细地介绍了基于层次图概念的三种算法,并通过例题来说明Dinic算法在信息学竞赛中的优越性。蒇肂螂薀芇[目录]膄袀一、引言 3罿二、预备概念 5蒄三、最短路径增值算法(MPLA)的步骤及复杂度分析 8芅四、Dinic算法的步骤以及复杂度分析 13芇五、Dinic算法在信息学竞赛中的应用 15羅例题1最大获利(profit) 15肅例题2矩阵游戏 18螂六、MPM的算法步骤以及复杂度分析 20袃七、总结 21羀[正文]莀引言蒆羄图论这门古老而又年轻的学科节图论这门学科的诞生始于18世纪欧拉证明了七桥问题,发表《依据几何位置的解题方法》一文。但图论的真正发展是从20世纪五六十年代开始的。所以说,图论是一门既古老又年轻的学科。在信息学竞赛中占据了相当大的比重。其中,网络流算法经常在题目中出现。网络流涵盖的知识非常丰富,从基本的最小割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等,同学们在平时需要多多涉猎这方面的知识,不断积累,才能应对题目的各种变化。衿随着信息学竞赛的不断发展,其题目的难度以及考察范围都不断增大。现在,对于一些新出现的题目,仅仅掌握最朴素的网络流算法并不足以解决问题。本文针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的3个网络流算法,并通过列举和比较说明了其在解题中的应用,而对一些基础的知识,如最小割最大流定理等,没有作具体阐释,大家可以在许多其他网络流资料中找到。膆螁莁二、预备概念芈本文对一些基本的理论,如最大流最小割定理等,不做阐述,读者可以参阅相关网络流资料。、源点、汇点、容量函数,以及其上的流量函数。我们这样定义对应的剩余图:剩余图中的点集与流量网络中的点集相同,即。对于流量网络中的任一条边蕿本文中所有涉及到的边若无指明均为有向边。,若,那么边,这条边在剩余图中的权值为;同时,若那么边,这条边在剩余图中的权值为。蚈我们可以发现,流量网络中的每条边在剩余图中都化作一条或二条边。剩余图中的每条边都表示在原流量网络中能沿其方向增广。剩余图的权值函数表示在流量网络中能够沿着的方向增广大小为的流量。所以在剩余图中,从源点到汇点的任意一条简单路径蚇简单路径:路径中不存在重复的顶点或边都对应着一条增广路,路径上每条边的权值的最小值即为能够一次增广的最大流量。,我们把从源点到点的最短路径长度称作点的层次,记为。源点的层次为0。在下面这张剩余图中:蚁羀源点薇0膈2螃1莂3芀3每个点旁边的数字即表示该点在图中的层次。:对于剩余图中的一条边,当且仅当时,边;虿直观地讲,层次图是建立在剩余图基础之上的一张“最短路图”。从源点开始,在层次图中沿着边不管怎么走,经过的路径一定是终点在剩余图中的最短路。,当该网络的层次图中不存在增广路时,我们称流函数为层次图的阻塞流。聿膅三、最短路径增值算法(MPLA)、初始化流量,计算出剩余图蒈2、根据剩余图计算层次图。若汇点不在层次图内,则算法结束袅3、在层次图内不断用bfs增广,直到层次图内没有增广路为止蚄4、转步骤2肀之前我们讲到的层次图将被应用在最短路径增值算法中。首先,我们看一下最短路径增值算法的步骤:羇蚅蒂蒂莇莆薃薁肀算法中,2、3步被循环执行,我们将执行2、3步的一次循环称为一个阶段。每个阶段中,我们首先根据剩余图建立层次图,然后不断用bfs在层次图内增广,寻找阻塞流。增广完毕后,进入下一个阶段。这样不断重复,直到汇点不在层次图内出现为止。汇点不在层次图内意味着在剩余图中不存在一条从源点到汇点的路径,即没有增广路。肆在程序实现的时候,层次图并不用被“建”出来,我们只需对每个顶点标记层次,增广的时候,判断边是否满足这一约束即可。:对于有n个点的流量网络,在最短路径增值算法中,最多有n个阶段。袇也就是说,在算法中层次图最多被建立n次。证明这个定理有助于我们进行算法复杂度分析。莂肁证明:罿在建立完层次图以后,假设从源点到汇点的最短路径长度为k,我们将层次图中所有的点分到k+1个集合中,第i个集合为,如下图所示:薇蒃{层次为0的顶点集合}膀{层次为1的顶点集合