《9.王欣上《浅谈基于分层思想的网络流算法》》.pdf

2007年全国信息学冬令营讲座 浅谈基于分层思想的网络流算法 上海市延安中学 王欣上 [关键字] 层次图 网络流 基本算法 应用 MPLA Dinic MPM [摘要] 本文详细地介绍了基于层次图概念的三种算法，并通过 例题来说明Dinic算法在信息学竞赛中的优越性。 [目录] 一、引言3 二、预备概念3 2.1剩余图的概念3 第 1 页 共 25 页 2007年全国信息学冬令营讲座 2.2顶点的层 4 2.3层次图的概念4 2.4 阻塞流的概念5 三、最短路径增值算法(MPLA)的步骤及复杂度分析5 3.1算法步骤5 3.2定理的证明6 3.3复杂度分析8 四、Dinic算法的步骤以及复杂度分析 9 4.1算法步骤9 4.2复杂度分析13 五、Dinic算法在信息学竞赛中的应用 15 例题1 最大获利(profit) 15 例题2 矩阵游戏18 六、MPM 的算法步骤以及复杂度分析19 6.1算法步骤19 6.2复杂度分析20 七、总结21 [正文] 一、引言 1 图论这门古老而又年轻的学科 在信息学竞赛中占据了相当大的比重。其中 ，网络流算法经常在题目中出现。网络流涵盖的知识非常丰富，从基本的最小 1 图论这门学科的诞生始于18世纪欧拉证明了七桥问题，发表《依据几何位置的解题方法》一文。但图论的 真正发展是从20世纪五六十年代开始的。所以说，图论是一门既古老又年轻的学科。 第 2 页 共 25 页 2007年全国信息学冬令营讲座 割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等，同学 们在平时需要多多涉猎这方面的知识，不断积累，才能应对题目的各种变化。 随着信息学竞赛的不断发展，其题目的难度以及考察范围都不断增大。现 在，对于一些新出现的题目，仅仅掌握最朴素的网络流算法并不足以解决问题 。本文针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的3个网 络流算法，并通过列举和比较说明了其在解题中的应用，而对一些基础的知识 ，如最小割最大流定理等，没有作具体阐释，大家可以在许多其他网络流资料 中找到。 二、预备概念1 2.1剩余图的概念 给定一个流量网络G  (E , V ) 、源点s 、汇点t 、容量函数c ，以及其上的 1 1 1 流量函数f 。我们这样定义对应的剩余图G  (E , V ) ：剩余图中的点集与流 2 2 2 2 量网络中的点集相同，即V  V 。对于流量网络中的任一条边 (u,v) E ，若 2 1 1 f (u,v)  c(u,v) ，那么边(u,v) E2 ，这条边在剩余图中的权值为 g (u,v)  c(u,v) f (u,v) ；同时，若f (u,v)  0 那么边(v,u) E2 ，这条边在剩余 图中的权值为g (v,u)  f (u,v) 。 我们可以发现，流量网络中的每条边在剩余图中都化作一条或二条边。剩 余图中的每条边都表示在原流量网络中能沿其方向增广。剩余图的权值函数 g (a,b) 表示在流量网络中能够沿着a到b 的方向增广大小为g (a,b) 的流量。所以 3 在剩余图中，从源点到