第 1 页 共 25 页
浅谈基于分层思想的网络流算法
[
[[
[关键字
关键字关键字
关键字]
]]
]
层次图 网络流 基本算法 应用
MPLA Dinic MPM
[
[[
[摘要
摘要摘要
摘要]
]]
]
本文详细地介绍了基于层次图概念的三种算法,并通过例
题来说明 Dinic 算法在信息学竞赛中的优越性。
第 2 页 共 25 页
[
[[
[目录
目录目录
目录]
]]
]
一、引言.....................................................................................................3
二、预备概念.............................................................................................3
2.1 剩余图的概念 ................................................................................3
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
第 3 页 共 25 页
[
[[
[正文
正文正文
正文]
]]
]
一
一一
一、
、、
、
引言
引言引言
引言
图论这门古老而又年轻的学科
①
在信息学竞赛中占据了相当大的比重。其中,
网络流算法经常在题目中出现。网络流涵盖的知识非常丰富,从基本的最小割最
大流定理到网络的许多变形再到最高标号预流推进的六个优化等等,同学们在平
时需要多多涉猎这方面的知识,不断积累,才能应对题目的各种变化。
随着信息学竞赛的不断发展,其题目的难度以及考察范围都不断增大。现在,
对于一些新出现的题目,仅仅掌握最朴素的网络流算法并不足以解决问题。本文
针对一些数据规模比较大的网络流题目详细介绍了基于分层思想的 3 个网络流
算法,并通过列举和比较说明了其在解题中的应用,而对一些基础的知识,如最
小割最大流定理等,没有作具体阐释,大家可以在许多其他网络流资料中找到。
二
二二
二、
、、
、预备
预备预备
预备概念
概念概念
概念
②
②②
②
2.1 剩余图
剩余图剩余图
剩余图的概念
的概念的概念
的概念
给定一个流量网络 ),(
111
VEG
=
、源点
s
、汇点
t
、容量函数
c
,以及其上的
流量函数 f 。我们这样定义对应的剩余图 ),(
222
VEG
=
:剩余图中的点集与流量
网络中的点集相同,即
12
VV
=
。对于流量网络中的任一条边
③
1
),( Evu
∈
,若
),(),( vucvuf
<
, 那 么 边
2
),( Evu
∈
, 这 条 边 在 剩 余 图 中 的 权 值 为
①
图论这门学科的诞生始于 18 世纪欧拉证明了七桥问题,发表《依据几何位置的解题方法》一文。但图论
的真正发展是从 20 世纪五六十年代开始的。所以说,图论是一门既古老又年轻的学科。
②
本文对一些基本的理论,如最大流最小割定理等,不做阐述,读者可以参阅相关网络流资料。
③
本文中所有涉及到的边若无指明均为有向边。
第 4 页 共 25 页
),(),(),( vufvucvug
−
=
;同时,若 0),(
>
vuf 那么边
2
),( Euv
∈
,这条边在剩余图
中的权值为 ),(),( vufuvg
=
。
我们可以发现,流量网络中的每条边在剩余图中都化作一条或二条边。剩余
图中的每条边都表示在原流量网络中能沿其方向增广。剩余图的权值函数 ),( bag
表示在流量网络中能够沿着 ba到 的方向增广大小为 ),( bag 的流量。所以在剩余
图中,从源点到汇点的任意一条简单路径
①
都对应着一条增广路,路径上每条边
的权值的最小值即为能够一次增广的最大流量。
2.2 顶点的层次
顶点的层次顶点的层次
顶点的层次
在剩余图中,我们把从源点到点
u
的最短路径长度称作点
u
的层次,记为
)(ulevel 。源点的层次为 0。在下面这张剩余图中:
每个点旁边的数字即表示该点在图中的层次。
2.3 层次图
层次图层次图
层次图的概念
的概念的概念
的概念
我们这样定义层次图 ),(
333
EVG
=
:对于剩余图 ),(
222
EVG
=
中的一条边
),( vu ,当且仅当 )(1)( vlevelulevel
=
+
时,边
3
),( Evu
∈
; }|{
33
相连中有边与uEuV
=
①
简单路径:路径中不存在重复的顶点或边
源点
0
2
1
3
3
汇点
第 5 页 共 25 页
直观地讲,层次图是建立在剩余图基础之上的一张“最短路图”。从源点开
始,在层次图中沿着边不管怎么走,经过的路径一定是终点在剩余图中的最短路。
2.4 阻塞流的概念
阻塞流的概念阻塞流的概念
阻塞流的概念
在流量网络中存在一可行流 f ,当该网络的层次图
3
G 中不存在增广路时,
我们称流函数 f 为层次图
3
G 的阻塞流。
三
三三
三、
、、
、最短路径增值算法
最短路径增值算法最短路径增值算法
最短路径增值算法(MPLA)的步骤及复
的步骤及复的步骤及复
的步骤及复
杂度分析
杂度分析杂度分析
杂度分析
3.1 算法步骤
算法步骤算法步骤
算法步骤
之前我们讲到的层次图将被应用在最短路径增值算法中。首先,我们看一下
最短路径增值算法的步骤:
算法中,2、3 步被循环执行,我们将执行 2、3 步的一次循环称为一个阶段
阶段阶段
阶段。
。。
。
每个阶段中,我们首先根据剩余图建立层次图,然后不断用 bfs 在层次图内增广,
寻找阻塞流。增广完毕后,进入下一个阶段。这样不断重复,直到汇点不在层次
图内出现为止。汇点不在层次图内意味着在剩余图中不存在一条从源点到汇点的
1、初始化流量,计算出剩余图
2、根据剩余图计算层次图。若汇点不在层次图
内,则算法结束
3、在层次图内不断用 bfs 增广,直到层次图内没
有增广路为止
4、转步骤 2