算法合集之《浅谈基于分层思想的网络流算法》

2007年全国信息学冬令营讲座第1页共26页浅谈基于分层思想的网络流算法上海市延安中学王欣上[关键字]层次图网络流基本算法应用MPLADinicMPM[摘要]本文详细地介绍了基于层次图概念的三种算法，并通过例题来说明Dinic算法在信息学竞赛中的优越性。2007年全国信息学冬令营讲座第2页共26页[目录]一、引言.....................................................................................................3二、预备概念.............................................................................................32.1剩余图的概念................................................................................32.2顶点的层次....................................................................................42.3层次图的概念................................................................................42.4阻塞流的概念................................................................................5三、最短路径增值算法(MPLA)的步骤及复杂度分析..........................53.1算法步骤........................................................................................53.2定理的证明....................................................................................63.3复杂度分析....................................................................................9四、Dinic算法的步骤以及复杂度分析................................................104.1算法步骤......................................................................................104.2复杂度分析..................................................................................14五、Dinic算法在信息学竞赛中的应用................................................16例题1最大获利(profit)....................................................................16例题2矩阵游戏...............................................................................19六、MPM的算法步骤以及复杂度分析................................................206.1算法步骤......................................................................................206.2复杂度分析..................................................................................212007年全国信息学冬令营讲座第3页共26页七、总结...................................................................................................22[正文]一、引言图论这门古老而又年轻的学科①在信息学竞赛中占据了相当大的比重。其中，网络流算法经常在题目中出现。网络流涵盖的知识非常丰富，从基本的最小割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等，同学们在平时需要多多涉猎这方面的知识，不断积累，才能应对题目的各种变化。随着信息学竞赛的不断发展，其题目的难度以及考察范围都不断增大。现在，对于一些新出现的题目，仅仅掌握最朴素的网络流算法并不足以解决问题。本文针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的3个网络流算法，并通过列举和比较说明了其在解题中的应用，而对一些基础的知识，如最小割最大流定理等，没有作具体阐释，大家可以在许多其他网络流资料中找到。二、预备概念②2.1剩余图的概念给定一个流量网络),(111VEG、源点s、汇点t、容量函数c，以及其上的流量函数f。我们这样定义对应的剩余图),(222VEG：剩余图中的点集与流量网络中的点集相同，即12VV。对于流量网络中的任一条边③1),(Evu，若①图论这门学科的诞生始于18世纪欧拉证明了七桥问题，发表《依据几何位置的解题方法》一文。但图论的真正发展是从20世纪五六十年代开始的。所以说，图论是一门既古老又年轻的学科。②本文对一些基本的理论，如最大流最小割定理等，不做阐述，读者可以参阅相关网络流资料。③本文中所有涉及到的边若无指明均为有向边。2007年全国信息学冬令营讲座第4页共26页),(),(vucvuf，那么边2),(Evu，这条边在剩余图中的权值为),(),(),(vufvucvug；同时，若0),(vuf那么边2),(Euv，这条边在剩余图中的权值为),(),(vufuvg。我们可以发现，流量网络中的每条边在剩余图中都化作一条或二条边。剩余图中的每条边都表示在原流量网络中能沿其方向增广。剩余图的权值函数),(bag表示在流量网络中能够沿着ba到的方向增广大小为),(bag的流量。所以在剩余图中，从源点到汇点的任意一条简单路径①都对应着一条增广路，路径上每条边的权值的最小值即为能够一次增广的最大流量。2.2顶点的层次在剩余图中，我们把从源点到点u的最短路径长度称作点u的层次，记为)(ulevel。源点的层次为0。在下面这张剩余图中：每个点旁边的数字即表示该点在图中的层次。2.3层次图的概念我们这样定义层次图),(333EVG：对于剩余图),(222EVG中的一条边①简单路径：路径中不存在重复的顶点或边源点02133汇点2007年全国信息学冬令营讲座第5页共26页),(vu，当且仅当)(1)(vlevelulevel时，边3),(Evu；}|{33相连中有边与uEuV直观地讲，层次图是建立在剩余图基础之上的一张“最短路图”。从源点开始，在层次图中沿着边不管怎么走，经过的路径一定是终点在剩余图中的最短路。2.4阻塞流的概念在流量网络中存在一可行流f，当该网络的层次图3G中不存在增广路时，我们称流函数f为层次图3G的阻塞流。三、最短路径增值算法(MPLA)的步骤及复杂度分析3.1算法步骤之前我们讲到的层次图将被应用在最短路径增值算法中。首先，我们看一下最短路径增值算法的步骤：算法中，2、3步被循环执行，我们将执行2、3步的一次循环称为一个阶段。每个阶段中，我们首先根据剩余图建立层次图，然后不断用bfs在层次图内增广，寻找阻塞流。增广完毕后，进入下一个阶段。这样不断重复，直到汇点不在层次1、初始化流量，计算出剩余图2、根据剩余图计算层次图。若汇点不在层次图内，则算法结束3、在层次图内不断用bfs增广，直到层次图内没有增广路为止4、转步骤22007年全国信息学冬令营讲座第6页共26页图内出现为止。汇点不在层次图内意味着在剩余图中不存在一条从源点到汇点的路径，即没有增广路。在程序实现的时候，层次图并不用被“建”出来，我们只需对每个顶点标记层次，增广的时候，判断边是否满足)(1)(vlevelulevel这一约束即可。3.2定理的证明定理：对于有n个点的流量网络，在最短路径增值算法中，最多有n个阶段。也就是说，在算法中层次图最多被建立n次。证明这个定理有助于我们进行算法复杂度分析。证明：在建立完层次图以后，假设从源点到汇点的最短路径长度为k，我们将层次图中所有的点分到k+1个集合中，第i个集合为}1)(|{iulevelu顶点，如下图所示：2007年全国信息学冬令营讲座第7页共26页在剩余图中，存在着2类边。第一类：从第i个集合中的顶点连到第)1(1kii个集合中的顶点第二类：从第)11(kii个集合中的顶点连到第)1(ijj个集合中的顶点在层次图中，只存在第一类边，这是由层次图的性质决定的。我们所要找的增广路中的边也必定是第一类边。当我们对一条增广路径增广后，会删除一条或多条增广路中的饱和边，也就是第一类边；而同时会在剩余图中加入一些与增广路径中的边反向的边。这些新加入的边一定是第二类边。如下图所示，在剩余图(a)中，找到一条从左向右的增广路径，能够增广的流量大小为2。增广后的结果是剩余图(b)。可以发现，在剩余图(a)里面，中间一条红色第一类边在增广后饱和而被删除了，同时，在剩余图(b)中，新增了2条绿色的第二类边。{层次为0的顶点集合}{层次为1的顶点集合}{层次为2的顶点集合}{层次为k-1的顶点集合}{层次为k的顶点集合}...2007年全国信息学冬令营讲座第8页共26页当我们在层次图中找到阻塞流之后，层次图中就不存在从第一个集合一步一步往下走，最后达到第k+1个集合的长为k的路径了。而此时不在层次图中的边都是第二类边。我们可以发现，这个时候在剩余图中的最短路径一定是这样：从源点开始，往下一步一步走，走到某个集合后沿着第二类边向上退至某个集合，再继续一步一步向下走，到某个集合又向上退…………直到走到汇点。因为必然会经过第二类边，而经过的第一类边的数量=k，所以路径总长度一定大于k。这即是下一个阶段的最短路径长度。由此，我们得出了一个结论：结论：层次图中增广路径长度随阶段而严格递增。因为增广路径长度最短是1，最长是n-1，再算上汇点不在层次图内的最后一次，层次图最多被建造n次，所以最短路径增值算法最多有n个阶段。证毕。6243源点汇点剩余图(a)5源点汇点剩余图(b)42222007年全国信息学冬令营讲座第9页共26页3.3复杂度分析3.3.1建造层次图的复杂度分析我们将复杂度分析分为建层次图和找增广路两部分讨论。前面已经证明了，在最短路径增值算法中，最多建n个层次图，每个层次图用bfs一次遍历即可得到。一次bfs遍历的复杂度为)(mO，所以建层次图的总复杂度为)*(mnO。3.3.2增广复杂度分析我们首先分析在每一阶段中找增广路的复杂度。注意到每增广一次，层次图中必定有一条边会被删除。层次图中最多有m条边，所以可以认为最多增广m次。在最短路径增广中，我们用bfs来增广。一次增广的复杂度为)(nmO。其中)(mO为bfs的花费，)(nO为修改流量的花费。所以在每一阶段的复杂度为)())(*(2mOmnmO这样，得到找增广路总的复杂度为)*(2mnO最短路径增值算法的总复杂度即为建层次图的总复杂度与找增广路的总复杂度之和，为)*(2mnO。2007年全国信息学冬令营讲座第10页共26页四、Dinic算法的步骤以及复杂度分析4