网络流基本概念及求法

大家好，欢迎来到IT知识分享网。
1. 容量网络和网络最大流

容量网络（capacity network）：设G(V, E)是一个有向网络，在V 中指定了一个顶点，称为源
点（记为Vs），以及另一个顶点，称为汇点（记为Vt）；对于每一条弧<u, v>∈E，对应有一个权值

c(u, v)＞0，称为弧的容量（capacity）。通常把这样的有向网络G 称为容量网络。

最大流（maximum flow）：在容量网络G(V, E)中，满足弧流量限制条件和平衡条件、且具有
最大流量的可行流，称为网络最大流，简称最大流。

2. 链与增广路
在容量网络G(V, E)中，设有一可行流f = { f(u, v) }，根据每条弧上流量的多少、以及流量和
容量的关系，可将弧分四种类型：
1) 饱和弧， 即f(u, v) = c(u, v)；
2) 非饱和弧，即f(u, v) < c(u, v)；
3) 零流弧， 即f(u, v) =0；
4) 非零流弧，即f(u, v) > 0。

链（chain）：在容量网络中，称顶点序列(u, u1, u2, …, un, v)为一条链，要求相邻两个顶点之间
有一条弧，如< u, u1>或< u1, u >为容量网络中一条弧。

1) 前向弧（方向与链的正方向一致的弧），其集合记为P+；
2) 后向弧（方向与链的正方向相反的弧），其集合记为P–。

增广路（augmenting path）：
设f 是一个容量网络G 中的一个可行流，P 是从Vs 到Vt 的一条链，若P 满足下列条件：
1) 在P 的所有前向弧<u, v>上，0 ≤ f(u, v) < c(u, v)，即P+中每一条弧都是非饱和弧；
2) 在P 的所有后向弧<u, v>上，0 < f(u, v) ≤ c(u, v)，即P–中每一条弧是非零流弧。

则称P 为关于可行流f 的一条增广路，简称为增广路（或称为增广链、可改进路）。

4. 割与最小割
割（cut）：在容量网络G(V, E)中，设E’⊆E，如果在G 的基图中删去E’后不再连通，则称E’
是G 的割。割将G 的顶点集V 划分成两个子集S 和T = V – S。将割记为(S, T)。
s-t 割：更进一步，如果割所划分的两个顶点子集满足源点Vs∈S，汇点Vt∈T，则称该割为
s-t 割。s-t 割(S, T)中的弧<u, v>(u∈S, v∈T)称为割的前向弧，弧<u, v>( u∈T, v∈S)称为割的反向弧。
（注意，在本章中，如无特别说明，所说的割均指s-t 割）
割的容量：设(S, T)为容量网络G(V, E)的一个割，其容量定义为所有前向弧的容量总和，用c(S,
T)表示。即：   c(S, T)＝Σc(u, v) u∈S，v∈T，<u, v>∈E。

最小割（minimum cut）：容量网络G(V, E)的最小割是指容量最小的割。
割的净流量。设f 是容量网络G(V, E)的一个可行流，(S, T)是G 的一个割，定义割的净流量f(S,
T)为：
f(S, T)＝Σf(u, v) u∈S，v∈T，<u, v>∈E 或<v, u>∈E。 (6-5)
注意：
(1) 在统计割的净流量时：在式(6-5)中，反向弧的流量为负值，即如果<v, u>∈E，那么在统
计割的净流量时f(u, v)是一个负值。
(2) 在统计割的容量时：在式(6-4)中，不统计反向弧的容量。

6.1.2 最大流最小割定理
如何判定一个网络流是否是最大流？有以下两个定理。
定理6.4（增广路定理） 设容量网络G(V, E)的一个可行流为f，f 为最大流的充要条件是在
容量网络中不存在增广路。
定理6.5（最大流最小割定理） 对容量网络G(V, E)，其最大流的流量等于最小割的容量。
根据定理6.4 和6.5，可以总结出以下4 个命题是等价的（设容量网络G(V, E)的一个可行流
为f）：
(1) f 是容量网络G 的最大流；
(2) | f |等于容量网络最小割的容量；
(3) 容量网络中不存在增广路；
(4) 残留网络G’中不存在从源点到汇点的路径。

6.1.3 网络最大流的求解
给定一个容量网络G(V, E)，如何求其最大流是6.1 节的重点。网络最大流的求解主要有两大
类算法：增广路算法（augmenting path algorithm）和预流推进算法（preflow-push algorithm）。
1. 增广路算法
根据增广路定理，为了得到最大流，可以从任何一个可行流开始，沿着增广路对网络流进行
增广，直到网络中不存在增广路为止，这样的算法称为增广路算法。问题的关键在于如何有效地
找到增广路，并保证算法在有限次增广后一定终止。
增广路算法的基本流程是（如图6.8 所示）：
(1) 取一个可行流f 作为初始流（如果没有给定初始流，则取零流f= { 0 }作为初始流）；
(2) 寻找关于f 的增广路P，如果找到，则沿着这条增广路P 将f 改进成一个更大的流；
(3) 重复第(2)步直到f 不存在增广路为止。
增广路算法的关键是寻找增广路和改进网络流。

2. 预流推进算法
预流推进算法是从一个预流出发对活跃顶点沿着允许弧进行流量增广，每次增广称为一次推
进（push）。在推进过程中，流一定满足流量限制条件（式6-1），但一般不满足流量平衡条件（式
6-2），因此只是一个伪流。此外，如果一个伪流中，从每个顶点（除源点Vs、汇点Vt 外）流出的
流量之和总是小于等于流入该顶点的流量之和，称这样的伪流为预流（preflow）。因此这类算法被
称为预流推进算法。

6.1.4 一般增广路方法–Ford-Fulkerson 算法
在Ford-Fulkerson 算法中，寻找增广路和改进网络流的方法是标号法（label method），接下
来先看标号法的两个实例，再介绍标号法的运算过程和程序实现。

1. 标号法实例
以下两个实例分别从初始流为零流和非零流出发采用标号法求网络最大流。
(1) 标号法求最大流的实例1 － 初始流为零流。
如图6.9(a)所示，各条弧上的流量均为0，初始可行流f 为零流。
在图(b)中，对初始流f 进行第一次标号。每个顶点的标号包含两个分量：
1) 第一个分量指明它的标号从哪个顶点得到，以便找出可改进量；
2) 第二个分量是为确定可改进量α用的。
首先对源点Vs 进行标号，标号为(0, +∞)。每次标号，源点的标号总是(0, +∞)。其中第一个
分量为0，表示该顶点是源点；第二个分量为+∞，表示Vs 可以流出任意多的流量（只要从它发
出的弧可以接受）。

(2) 标号法求最大流的实例2 － 初始流为非零流。

其实这个就是零流标号法进行到哪一步为非零流的过程中的一步开始的……

2. 标号法的运算过程
标号法的具体运算过程如下：从一个可行流f 出发（若网络中没有给定每条弧的流量，则可
以设f 为零流），进入标号过程和调整过程。
(1) 标号过程
在标号过程，容量网络中的顶点可以分为三类：
① 未标号顶点；
② 已标号，未检查邻接顶点；
③ 已标号，且已检查邻接顶点（即已经检查它的所有邻接顶点，看是否能标号）。
每个标号顶点的标号包含两个分量：
1) 第一个分量指明它的标号从哪个顶点得到，以便找出增广路；
2) 第二个分量是为确定可改进量α用的。
标号过程开始时，总是先给Vs 标上(0, +∞)，0 表示Vs 是汇点，+∞表示Vs 可以流出任意多
的流量（只要从它发出的弧可以接受）。这时Vs 是已标号而末检查的顶点，其余都是末标号点。
然后从源点Vs 出发，对它的每个邻接顶点进行标号。
一般，取一个已标号而未检查的顶点u，对一切未标号顶点v：
a) 若v 与u“正向”邻接，且在弧<u, v>上f(u, v)＜c(u, v)，则给v 标号(u，L(v))，这里L(v)
= min{ L(u), c(u, v) – f(u, v) }，L(u)是顶点u 能提供的标号，c(u, v) – f(u, v)是弧<u, v >能接
受的标号，取二者中的较小者。这时顶点v 成为已标号而末检查的顶点。
b) 若v 与u“反向”邻接，且在弧< v, u>上f(v, u)＞0，则给v 标号( -u, L(v))，这里L(v) =
min{ L(u), f(v, u) }。这时顶点v 成为已标号而未检查的顶点。
当u 的全部邻接顶点都已检查后，u 成为已标号且已检查过的顶点。
重复上述步骤直至汇点获得标号，一旦汇点Vt 被标号并且汇点标号的第2 个分量大于0，则
表明得到一条从Vs 到Vt 的增广路P，转入调整过程；若所有已标号未检查的顶点都检查完毕但标
号过程无法继续、从而汇点Vt 无法获得标号，或者得到的可改进量α= 0，则算法结束，这时的可
行流即为最大流。

(2) 调整过程
采用“倒向追踪”的方法，从Vt 开始，利用标号顶点的第一个分量逐条弧地找出增广路P，
并以Vt 的第二个分量L(Vt)作为改进量α，改进P 路上的流量。
例如，设Vt 标号的第一个分量为Vk，则弧<Vk, Vt>是增广路P 上的弧。接下来检查Vk 标号的
第一个分量，若为Vi（或-Vi），则找到弧<Vi, Vk>（或相应的<Vk, Vi>）。再检查Vi 标号的第一个分
量，…，一直到Vs 为止。这时被找出的弧就构成了增广路P。改进量α 是L(Vt)，即Vt 标号的第二
个分量。对这条增广路上各条弧的流量作如下调整：

前向弧：f(u,v)+=a;

3. 标号法的程序实现
例6.1 利用前面介绍的标号法求图6.9(a)及6.10(a)所示的容量网络的最大流，输出各条弧及
其流量，以及求得的最大流流量。
假设数据输入时采用如下的格式进行输入：首先输入顶点个数n 和弧数m，然后输入每条弧
的数据。规定源点为第0 个顶点、汇点为第n-1 个顶点。每条弧的数据格式为：u v c f，分别表示
这条弧的起点、终点、容量和流量。顶点序号从0 开始计起。

代码如下：

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <list> #include <queue> #include <string> #include <cstring> #include <map> #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define pri(a) printf("%d\n",a) #define M 1002 #define INF  using namespace std; typedef long long ll; struct ArcType //弧结构 { int c, f; //容量，流量 } Edge[M][M]; //邻接矩阵(每个元素为ArcType 类型) int n, m; //顶点个数和弧数 int flag[M]; //顶点状态：-1－未标号,0－已标号未检查,1－已标号已检查 int prev[M]; //标号的第一个分量：指明标号从哪个顶点得到，以便找出可改进量 int alpha[M]; //标号的第二个分量：可改进量α int Queue[M]; //相当于BFS 算法中的队列 int v; //从队列里取出来的队列头元素 int qs, qe; //队列头位置，队列尾位置 int i, j; //循环变量 void ford( ) { while( 1 ) //标号直至不存在可改进路 { //标号前对顶点状态数组初始化 memset( flag, 0xff, sizeof(flag) ); //将3 个数组各元素初始化为-1 memset( prev, 0xff, sizeof(prev) ); memset( alpha, 0xff, sizeof(alpha) ); flag[0] = 0; prev[0] = 0; alpha[0] = INF; //源点为已标号未检查顶点 qs = qe = 0; Queue[qe] = 0; qe++; //源点(顶点0)入队列 //qs<qe 表示队列非空, flag[n-1]==-1 表示汇点未标号 while( qs<qe && flag[n-1]==-1 ) { v = Queue[qs]; qs++; //取出队列头顶点 for( i=0; i<n; i++ ) //检查顶点v 的正向和反向"邻接"顶点 { if( flag[i]==-1 ) //顶点i 未标号 { if( Edge[v][i].c<INF && Edge[v][i].f < Edge[v][i].c ) //"正向"且未"满" { flag[i] = 0; prev[i] = v; //给顶点i 标号(已标号未检查) alpha[i] = min( alpha[v], Edge[v][i].c - Edge[v][i].f ); Queue[qe] = i; qe++;//顶点i 入队列 } else if( Edge[i][v].c<INF && Edge[i][v].f > 0 )//"反向"且有流量,因为有流量才得减a { flag[i] = 0; prev[i] = -v; //给顶点i 标号(已标号未检查) alpha[i] = min( alpha[v], Edge[i][v].f ); Queue[qe] = i; qe++;//顶点i 入队列 } } } flag[v] = 1; //顶点v 已标号已检查 }//end of while( qs<qe && flag[n-1]==-1 ) //当汇点没有获得标号，或者汇点的调整量为0，应该退出while 循环 if( flag[n-1]==-1 || alpha[n-1]==0 ) break; //当汇点有标号时,应该进行调整了 int k1 = n-1, k2 = abs( prev[k1] ); int a = alpha[n-1]; //可改进量 while( 1 ) { if( Edge[k2][k1].f<INF ) //正向 Edge[k2][k1].f = Edge[k2][k1].f + a; else Edge[k1][k2].f = Edge[k1][k2].f - a; //反向 if( k2==0 ) break; //调整一直到源点v0 k1 = k2; k2 = abs( prev[k2] ); }//end of while( 1 ) }//end of while( 1 ) //输出各条弧及其流量，以及求得的最大流量 int maxFlow = 0; for( i=0; i<n; i++ ) { for( j=0; j<n; j++ ) { if( i==0 && Edge[i][j].f<INF )//求源点流出量，即最大流 maxFlow += Edge[i][j].f; if( Edge[i][j].f<INF ) printf( "%d->%d : %d\n", i, j, Edge[i][j].f ); } } printf( "maxFlow : %d\n", maxFlow ); } int main( ) { int u, v, c, f; //弧的起点、终点、容量、流量 scanf( "%d%d", &n, &m ); //读入顶点个数n 和弧数m for( i=0; i<n; i++ ) //初始化邻接矩阵中各元素 { for( j=0; j<n; j++ ) Edge[i][j].c = Edge[i][j].f = INF;//INF 表示没有直接边连接 } for( i=0; i<m; i++ ) //读入每条弧 { scanf( "%d%d%d%d", &u, &v, &c, &f ); //读入边的起点和终点 Edge[u][v].c = c; Edge[u][v].f = f; //构造邻接矩阵 } ford( ); //标号法求网络最大流 return 0; }