文档介绍：算法合集之《浅谈基于分层思想的网络流算法》
2
———————————————————————————————— 作者：
———————————————————————————————— 日期：
个人收集 仅供参考学****勿做商业用途
浅谈基于分层思想的网络流算法
上海市延安中学 王欣上
[关键字]
层次图 网络流 根本算法 应用
MPLA Dinic MPM
[摘要]
本文详细地介绍了基于层次图概念的三种算法，并通过例题来说明Dinic算法在信息学竞赛中的优越性。
3
个人收集 仅供参考学****勿做商业用途
[目录]
一、引言 3
二、预备概念 3
剩余图的概念 3
顶点的层次 4
层次图的概念 4
阻塞流的概念 5
三、最短路径增值算法(MPLA)的步骤及复杂度分析 5
算法步骤 5
定理的证明 6
复杂度分析 8
四、Dinic算法的步骤以及复杂度分析 9
算法步骤 9
复杂度分析 13
五、Dinic算法在信息学竞赛中的应用 15
例题1 最大获利(profit) 15
例题2 矩阵游戏 18
六、MPM的算法步骤以及复杂度分析 19
算法步骤 19
复杂度分析 20
5
个人收集 仅供参考学****勿做商业用途
七、总结 21
[正文]
引言
图论这门古老而又年轻的学科 图论这门学科的诞生始于18世纪欧拉证明了七桥问题，发表?依据几何位置的解题方法?一文。但图论的真正开展是从20世纪五六十年代开场的。所以说，图论是一门既古老又年轻的学科。
在信息学竞赛中占据了相当大的比重。其中，网络流算法经常在题目中出现。网络流涵盖的知识非常丰富，从根本的最小割最大流定理到网络的许多变形再到最高标号预流推进的六个优化等等，同学们在平时需要多多涉猎这方面的知识，不断积累，才能应对题目的各种变化。
随着信息学竞赛的不断开展，其题目的难度以及考察范围都不断增大。现在，对于一些新出现的题目，仅仅掌握最朴素的网络流算法并缺乏以解决问题。本文针对一些数据规模比拟大的网络流题目详细介绍了基于分层思想的3个网络流算法，并通过列举和比拟说明了其在解题中的应用，而对一些根底的知识，如最小割最大流定理等，没有作具体阐释，大家可以在许多其他网络流资料中找到。
二、预备概念 本文对一些根本的理论，如最大流最小割定理等，不做阐述，读者可以参阅相关网络流资料。
给定一个流量网络、源点、汇点、容量函数，以及其上的流量函数。我们这样定义对应的剩余图：剩余图中的点集与流量网络中的点集一样，即。对于流量网络中的任一条边 本文中所有涉及到的边假设无指明均为有向边。
，假设
5
个人收集 仅供参考学****勿做商业用途
，那么边，这条边在剩余图中的权值为；同时，假设那么边，这条边在剩余图中的权值为。
我们可以发现，流量网络中的每条边在剩余图中都化作一条或二条边。剩余图中的每条边都表示在原流量网络中能沿其方向增广。剩余图的权值函数表示在流量网络中能够沿着的方向增广阔小为的流量。所以在剩余图中，从源点到汇点的任意一条简单路径 简单路径：路径中不存在重复的顶点或边
都对应着一条增广路，路径上每条边的权值的最小值即为能够一次增广的最大流量。
汇点
在剩余图中，我们把从源点到点的最短路径长度称作点的层次，记为。源点的层次为0。在下面这张剩余图中：
源点
0
2
1
3
3
每个点旁边的数字即表示该点在图中的层次。
6