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

2007 年全国信息学冬令营讲座

浅谈基于分层思想的网络流算法

上海市延安中学 王欣上

[关键字]

层次图 网络流 基本算法 应用

MPLA Dinic MPM

[摘要]

本文详细地介绍了基于层次图概念的三种算法，并通过

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

2007 年全国信息学冬令营讲座

七、总结..................................................................................................21

[正文]

一、引言

2007 年全国信息学冬令营讲座

二、预备概念

2.1 剩余图的概念

， 那 么 边

， 这 条 边 在 剩 余 图 中 的 权 值 为

表示在流量网络中能够沿着

的方向增广大小为

以在剩余图中，从源点到汇点的任意一条简单路径

都对应着一条增广路，路径

上每条边的权值的最小值即为能够一次增广的最大流量。

2.2 顶点的层次

在剩余图中，我们把从源点到点

的层次，记为

2007 年全国信息学冬令营讲座

2.3 层次图的概念

中的一条边

， 当 且 仅 当

时 ， 边

；

我们称流函数

为层次图

的阻塞流。

源点

0

2

1