当前位置：文档之家› 网络流算法和PASCAL程序

网络流算法和PASCAL程序

网络流算法及其应用

网络流

网络流 network flows网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

定义

图论中的一种理论与方法，研究网络上的一类最优化问题。1955年，T.E. 哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D＝（V、E、C），其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1 (v6)

表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短???这样一类问题称为最短路问题。如果把上图看作一个输油管道网， v1 表示发送点，v6表示接收点，其他点表示中转站，各边的权数

寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。

增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1（假设容量、流为整数），这样会造成性能上的很大问题，解决这个问题有一个复杂得多的算法，就是预推进算法。

2、push label，直译为“预推进”算法。

3、压入与重标记(Push-Relabel)算法

除了用各种方法在剩余网络中不断找增广路(augmenting)的

Ford-Fulkerson系的算法外，还有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本操作有：压入，作用于一条边，将边的始点的预流尽可能多的压向终点；重标记，作用于一个点，将它的高度（也就是label）设为所有邻接点的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺点是相对难以理解。

Relabel-to-Front使用一个链表保存溢出顶点，用Discharge操作不断使溢出顶点不再溢出。Discharge的操作过程是：若找不到可被压入的临边，则重标记，否则对临边压入，直至点不再溢出。算法的主过程是：首先将源点出发的所有边充满，然后将除源和汇外的所有顶点保存在一个链表里，从链表头开始进行Discharge，如果完成后顶点的高度有所增加，则将这个顶点置于链表的头部，对下一个顶点开始Discharge。

Relabel-to-Front算法的时间复杂度是O(V^3)，还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP，感觉它和Relabel-to-Front本质上没有区别，因为Relabel-to-Front 每次前移的都是高度最高的顶点，所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点，每次对pop出来的顶点discharge，出现了新的溢出顶点时入队。

Push-Relabel类的算法有一个名为gap heuristic的优化，就是当存在一个整数0k的顶点v 做更新，若它小于V+1就置为V+1。

cpp程序:

#include

const long maxn=1000+10;

const long maxm=440000+100;

const long maxnum=100000000;

long

n,m,s=0,tot=0,list[maxn],p[maxn],g[maxn],gg[maxn],dis[maxn];

bool mark[maxn];

struct node

{

long k,f,c,next,g;

}d[maxm<<1];

void insert(long u,long v,long c)

{

d[tot].k=v;

d[tot].f=0;

d[tot].c=c;

d[tot].next=g;

g=tot;

d[tot].g=tot+1;

tot++;

d[tot].k=u;

d[tot].f=0;

d[tot].c=0;

d[tot].next=g[v];

g[v]=tot;

d[tot].g=tot-1;

tot++;

}

void bfs()

{

long x,u,v,h,t;

for (long i=0;i

dis=0;

h=0;

t=1;

list[1]=0;

编辑本段最小费用最大流

一．Ford和Fulkerson迭加算法.

基本思路：把各条弧上单位流量的费用看成某种长度,用求解最短路问题的方法确定一条自V1至Vn的最短路;在将这条最短路作为可扩充路,用求解最大流问题的方法将其上的流量增至最大可能值;而这条最短路上的流量增加后,其上各条弧的单位流量的费用要重新确定,如此多次迭代,最终得到最小费用最大流.

迭加算法：

1) 给定目标流量F或∞,给定最小费用的初始可行流=0

2) 若V(f)=F,停止,f为最小费用流;否则转(3).

3) 构造相应的新的费用有向图W(fij),在W(fij)寻找Vs到Vt的最小费用有向路P(最短路),沿P增加流f的流量直到F,转(2);若不存在从Vs到Vt的最小费用的有向路P,停止.f就是最小费用最大流.

具体解题步骤：

设图中双线所示路径为最短路径，费用有向图为W（fij）．

在图(a)中给出零流 f,在图(b)中找到最小费用有向路,修改图(a)中的可行流,δ=min{4,3,5}=3,得图(c),再做出(c)的调整容量图,再构造相应的新的最小费用有向路得图(d), 修改图(c)中的可行流, δ=min{1,1,2,2}=1,得图(e),以此类推,一直得到图(h),在图(h)中以无最小费用有向路,停止,

经计算:

图(h)中最小费用=1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38

图(g)中最大流=5

最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那么这个问题就变成最短路问题。由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流(或最小费用最大流)问题，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。

二．圈算法：

1) 利用Ford和Fulkson标号算法找出流量为F(<=最大流)的流f.

2) 构造f对应的调整容量的流网络N'(f).

3) 搜索N'(f)中的负费用有向图C(Floyd算法),若没有则停止,否则转

(4).

4) 在C上找出最大的循环流,并加到N上去,同时修改N'(F)中C的容量,转(3).

具体解题步骤:

利用Ford和Fulkson标号算法,得网络的最大流F=5,见图(a),由图(a)构造相应的调整容量的流网络(b),图(b)中不存在负费用有向图,故停止．经计算:

图(b)中最小费用= 4*1+3*1+1*1+3*3+4*2+1*1+4*1+2*4=38

图(a)中最大流为F=5

Type

szbest=record

v,l:integer;

end;

szmap=record

c,f,w:integer;

end;

Var

map:array[0..1000,0..1000] of szmap;

best:array[0..1000] of szbest;

i,j,ans,n,k,a,b,c,d,s,t:integer;

Function find:boolean;

var i,j:integer;

flag:boolean;

begin

for i:=1 to n do best.v:=maxint;

best[s].v:=0;

repeat

flag:=true;

for i:=1 to n do

if best.v

for j:=1 to n do

if (map[i,j].f

begin

best[j].v:=best.v+map[i,j].w;

best[j].l:=i; flag:=false;

end;

until flag;

if best[t].v

else exit(false);

end;

Procedure updata;

var i,j:integer;

begin

i:=t;

while i<>s do

begin

j:=best.l;

inc(map[j,i].f);

map[i,j].f:=-map[j,i].f;

i:=j;

end;

inc(ans,best[t].v);

end;

begin {main}

assign(input,'g4.in');reset(input);

assign(output,'g4.out');rewrite(output);

readln(n);

repeat

readln(a,b,c,d);

if a+b+c+d>0 then

begin

map[a,b].c:=c; map[b,a].c:=0;

map[a,b].w:=d; map[b,a].w:=-d;

end;

until a+b+c+d=0;

s:=1; t:=n; ans:=0;

while find do updata;

writeln(ans);

for i:=1 to n do

for j:=1 to n do

if map[i,j].f>0 then

writeln(i,' ',j,' ',map[i,j].w,'*',map[i,j].f);

close(input); close(output);

end.

三，ZKW费用流

费用流是网络流的一个很重要的组成部分，也是非常有用的一种图论模型，关于费用流的算法，流传比较广的主要是消圈和增广路算法，而近来炒得沸沸扬扬的ZKW算法也是一种非常优秀的算法，这里我就谈谈我对此算法的一些理解。

此算法是由ZKW大牛创立，主要思想仍然是找增广路，只是有了一些优化在里边。原来我们找增广路主要是依靠最短路算法，如SPFA。因此此算法的时间复杂度主要就取决于增广的次数和每次增广的耗费。由于每一次找增广路是都是重新算一遍，这样似乎显得有些浪费，如果我们能够缩短找增广路的时间，那必定会大大地优化算法。

值得注意的是，在寻求最短路得过程中，设dis[i]为i到起点的距离，对于每一条由i引向j的边，必有dis[j]<=dis[i]+map[i][j]；既然满足这样的恒等式，我们就可以借用KM算法的调整思想来寻求最短路，每次只走dis[j]=dis[i]+map[i][j]的路径，一旦不存在到达终点的路径，就扫描每一条边，找到最小的距离增加值，使得有至少一条新边被加入相等子图。

算法流程如下：

1.将dis数组清零，表示当前的相等子图内只有起点。

（如果存在负权边，必须要用spfa跑一遍，初始化出dis数组，下面的第二题就是这样的例子）。

2.深搜，如果到达终点，全部回退更改流量，再进行步骤2；否则，转3。

3.修改dis的值，如果无法修改，结束程序，已经找到的答案，反之转2。

编辑本段有上下界的最大流

v上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧加上一个下界限制Aij (即必须满足Aij≤fij)。

v弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了。

编辑本段网络流算法

一、网络流的基本概念

先来看一个实例。

现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下图：

每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？

这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。

若有向图G=(V,E)满足下列条件：

1、有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S 便称为源点，或称为发点。

2、有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T 便称为汇点，或称为收点。

3、每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij 表示。

则称之为网络流图，记为G = (V, E, C)

譬如图5-1就是一个网络流图。

1．可行流

对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。

1、每一条弧(i,j)有fij≤cij。

2、除源点S和汇点T以外的所有的点vi，恒有：

该等式说明中间点vi的流量守恒，输入与输出量相等。

3、对于源点S和汇点T有：

这里V(f)表示该可行流f的流量。

例如对图5-1而言，它的一个可行流如下：

流量V(f) = 5。

2．可改进路

给定一个可行流f=。若fij = cij，称为饱和弧；否则称为非饱和弧。若fij = 0，称为零流弧；否则称为非零流弧。

定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。

譬如在图5-1中，P = (S, V1, V2, V3, V4, T)，那么

P+ = {, , , }

P- = {}

给定一个可行流f，P是从S到T的一条道路，如果满足：

那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。具体方法下一节会重点介绍，此不赘述。

3．割切

要解决网络最大流问题，必须先学习割切的概念和有关知识。

G = (V, E, C)是已知的网络流图，设U是V的一个子集，W = V\U，满足S U，T W。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。

对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：

例如图5-1中，令U = {S, V1}，则W = {V2, V3, V4, T}，那么

C(U, W) = + + +=8+4+4+1=17 定理：对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有：V(f) ≤ C(U, W)。

通俗简明的讲：“最大流小于等于最小割”。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。

下面我们给出证明。

网络流、可改进路、割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。

二、求最大流

何谓最大流？首先它必须是一个可行流；其次，它的流量必须达到最大。这样的流就称为最大流。譬如对图5-1而言，它的最大流如下：下面探讨如何求得最大流。

在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则”。

对可改进路P上的弧，分为两种情况讨论：

第一种情况：∈P+，可以令fij增加一个常数delta。必须满足fij + delta ≤ ci j，即delta ≤ cij – fij。

第二种情况：∈P-，可以令fij减少一个常数delta。必须满足fij - delta ≥ 0，即delta ≤ fij

根据以上分析可以得出delta的计算公式：

因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，所以delta > 0。

容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”（即输入量等于输出量），又可以使得总的流量有所增加（因为delta > 0）。

因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在的问题是：倘若在f中找不到可改进路，是不是f就一定是最大流呢？

答案是肯定的。下面我们给出证明。

定理1 可行流f是最大流的充分必要条件是：f中不存在可改进路。

证明：

首先证明必要性：已知最大流f，求证f中不存在可改进路。

若最大流f中存在可改进路P，那么可以根据一定规则（详见上文）修改P中弧的流量。可以将f的流量放大，这与f是最大流矛盾。故必要性得证。

再证明充分性：已知流f，并且f中不存在可改进路，求证f是最大流。

我们定义顶点集合U, W如下：

（a）S∈U，

（b）若x∈U，且fxy

若x∈U，且fyx>0，则y∈U。

（这实际上就是可改进路的构造规则）

（c） W = V \ U。

由于f中不存在可改进路，所以T∈W；又S∈U，所以U、W是一个割切（U, W）。

按照U的定义，若x∈U，y∈W，则fxy = cxy。若x∈W，y∈U，则fxy = 0。

所以，

又因v(f)≤C(U,W)

所以f是最大流。得证。

根据充分性证明中的有关结论，我们可以得到另外一条重要定理：

最大流最小割定理：最大流等于最小割，即max V(f) = min C(U, W)。

至此，我们可以轻松设计出求最大流的算法：

step 1. 令所有弧的流量为0，从而构造一个流量为0的可行流f（称作零流）。

step 2. 若f中找不到可改进路则转step 5；否则找到任意一条可改进路P。

step 3. 根据P求delta。

step 4. 以delta为改进量，更新可行流f。转step 2。

step 5. 算法结束。此时的f即为最大流。

三、最小费用最大流

1．问题的模型

流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。

图5-8是一个最简单的例子：弧上标的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的花费，譬如fs1=4，所需花费为3*4=12。

容易看出，此图的最大流（流量是8）为：fs1 = f1t = 5, fs2 = f2t = 3。所以它的费用是：3*5+4*5+7*3+2*3 = 62。

一般的，设有带费用的网络流图G = (V, E, C, W)，每条弧对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足：

(a) 流量V(f)最大。

(b) 满足a的前提下，流的费用Cost(f) = 最小。

就称f是网络流图G的最小费用最大流。

2．算法设计

我们模仿求最大流的算法，找可改进路来求最小费用最大流。

设P是流f的可改进路，定义为P的费用（为什么如此定义？）。如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。

求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。

算法可描述为：

step 1. 令f为零流。

step 2. 若无可改进路，转step 5；否则找到最小费用可改进路，设为P。

step 3. 根据P求delta（改进量）。

step 4. 放大f。转step 2。

step 5. 算法结束。此时的f即最小费用最大流。

至于算法的正确性，可以从理论上证明。读者可自己思考或查阅有关运筹学资料。

2．最小费用可改进路的求解

求“最小费用可改进路”是求最小费用最大流算法的关键之所在，下面我们探讨求解的方法。

设带费用的网络流图G = (V, E, C, W)，它的一个可行流是f。我们构造带权有向图B = (V’, E’)，其中：

1、V’ = V。

2、若∈E，fij∈E’，权为Wij。

若∈E，fij>0，那么∈E’，权为-Wij。

显然，B中从S到T的每一条道路都对应关于f的一条可改进路；反之，关于f的每条可改进路也能对应B中从S到T的一条路径。即两者存在一一映射的逻辑关系。

故若B中不存在从S到T的路径，则f必然没有可改进路；不然，B中从S到T的最短路径即为f的最小费用可改进路。

现在的问题变成：给定带权有向图B = (V’, E’)，求从S到T的一条最短路径。

考虑到图中存在权值为负数的弧，不能采用Dijkstra算法；Floyd算法的效率又不尽如人意——所以，这里采用一种折衷的算法：迭代法。

设Short[k]表示从S到k顶点的最短路径长度；从S到顶点k的最短路径中，顶点k的前趋记为Last[k]。那么迭代算法描述如下：（为了便于描述，令n = |V’|，S的编号为0，T的编号为n+1）

0。?+∞（1≤k≤n+1），Short[0] ?step 1. 令Short[k] step 2. 遍历每一条弧。若Short[k] + < Short[k] +?Short[j]，则令Short[j] ?，同时Last[j] k。倘不存在任何一条弧满足此条件则转step 4。

step 3. 转step 2.

step 4. 算法结束。若Short[n + 1]= +∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。

一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n。

3．思维发散与探索

1）可改进路费用：“递增！递增？”

设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢？

2）迭代法：“小心死循环！嘿嘿……”

迭代法会出现死循环吗？也就是说，构造的带权有向图B中会存在负回路吗？

3）费用：“你在乎我是负数吗？”

网络流图中的费用可以小于零吗？

4）容量：“我管的可不仅是弧。”

网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制：即通过此顶点的流量的上限；任务仍然是求从S到T的最小费用最大流。你能解决吗？

四、有上下界的最大流

上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧加上一个下界限制Aij（即必须满足Aij≤fij）。

例如图5-9：

弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图5-10(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具体方案见图5-10(b)。

那么有上下界的网络最大流怎么求呢？

一种自然的想法是去掉下界，将其转化为只含上界的网络流图。这种美好的愿望是可以实现的。具体方法如下：

设原网络流图为G = (V, E, C, A)，构造不含下界的网络流图G’ = (V’, E’, C’)：

1、V’ = V∪{S’, T’}

2、对每个顶点x，令，若h-(x)≠0，就添加一条弧，其上界为h-(x)。

3、对每个顶点x，令，若h+(x)≠0，就添加一条弧，其上界为h+(x)。

4、对于任何∈E，都有∈E’，其上界C’ij = Cij – Aij。

5、新增∈E’，其上界CTS = +∞。

在G’中以S’为源点、T’为汇点求得最大流f’。若f’中从S’发出的任意一条弧是非饱和弧，则原网络流图没有可行流。否则可得原图的一个可行流f = f’ + A，即所有的fij = f’ij + Aij。（其正确性很容易证明，留给读者完成）

然后再求可改进路（反向弧必须满足fij≥Aij，而非fij≥0），不断放大f，直到求出最大流。

我们看到，上几节所讨论的一种可行网络流实际上是{Aij = 0}的一种特殊网络流，这里提出的模型更一般化了。解决一般化的复杂问题，我们采取的思路是将其转化为特殊的简单问题，加以研究、推广，进而解决。这是一种重要的基本思想：化归——简单有效。基于这种思想，请读者自行思考解决：

1、有上下界的最小流。

2、有上下界的最小费用最大流。

五、多源点、多汇点的最大流

已知网络流图有n个源点S1、S2、……、Sn，m个汇点T1、T2、……、Tm，，求该图的最大流。这样的问题称为多源点、多汇点最大流。

它的解决很简单：

1、增设一个“超级源”S’，对每个源点Si，新增弧，容量为无穷大。

2、增设一个“超级汇”T’，对每个汇点Ti，新增弧，容量为无穷大。

3、以S’为源点、T’为汇点求最大流f。

4、将f中的S’和T’去掉，即为原图的最大流。

算法正确性显然。

六、顶点有容量限制的最大流

上一节已经提出了这个问题，即对于进出每个顶点的流量也规定一个上限，这样的最大流如何求？

既然我们已经解决了“边限制”问题，现在何不把“点限制”问题转化为“边限制”呢？具体办法如下：

1、对除源点和汇点之外的每个顶点i拆分成两个顶点i’和i’’。新增一条弧，其容量为点i的流量限制。

2、对于原图中的弧，我们将其变换成。

3、对变换后的图求最大流即可。

这里我们又一次运用到了化归的思想：将未知的“点限制”问题转化为已知的“边限制”问题。

七、网络流与二部图的匹配

{二部图和匹配的定义可参见本书专门介绍二部图匹配的章节}

设二部图为G = (X, Y, E)。

增设点S’，对于所有i∈X，新增弧，容量为1；增设点T’，对于所有i∈Y，新增一条弧，容量也为1。原图中所有的弧予以保留，容量均为+∞。对新构造出来的网络流图以S’为源点、T’为汇点求最大流：流量即为最大匹配数；若弧（i∈X，j∈Y）的流量非零，它就是一条匹配边。

二部图最大匹配问题解决。

那么二部图的最佳匹配问题又如何？

仍然按照上述方法构图。同时令原图中弧的费用保持不变；新增弧的费用置为0。然后以S’为源点、T’为汇点求最小费用最大流即可。最大流的费用即为原二部图最佳匹配的费用。

八、网络流的应用（略）

5.1 基本概念

在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。

1.问题描述如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到

vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。

图5-1 图5-2

2.网络与网络流

给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。

3.可行流与最大流

在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：

(1)容量约束：0≤f ij≤c ij，(v i,v j)∈E，

(2)守恒条件

对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量v s(f)=汇点的净流入量（-v t(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。

网络N中流值最大的流f*称为N的最大流。

4.可增广路径

所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。

设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：

(1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤f ij

(2)在p上的所有后向弧(vi←vj)都是非零弧，即0

则称p为(关于可行流f的)一条可增广路径。

5.最大流定理

当且仅当不存在关于f*的增广路径，可行流f*为最大流。

5. 2 最大流算法

算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f，得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。

1.寻求最大流的标号法(Ford,Fulkerson)

从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f 的可增广路径为止。

(1)标号过程

在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。

标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。

取一个标号而未检查的点vi，对于一切未标号的点vj：

A．对于弧(vi，vj)，若fij

B．对于弧(vi，vj)，若fji>0，则给vj标号(-vi，0)，这时，vj点成为标号而未检查的点。

于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。

若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。

(2)调整过程

从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：

Q=min{min(cij-fij)，minf*ij}

对流f进行如下的修改：

f'ij = fij+Q (vi，vj)∈P的前向弧的集合

f'ij = fij-Q (vi，vj)∈P的后向弧的集合

f'ij = f*ij (vi，vj)不属于P的集合

接着，清除所有标号，对新的可行流f’，重新进入标号过程。

例1:下图表示一个公路网,V1是某原材料产地,V6表示港口码头,每段路的通过能力(容量)如图上的各边上的数据,找一运输方案,使运输到码头的原材料最多?

程序如下:

Program Max_Stream;

Const Maxn=20;

type

nettype=record