例题最大流的标号法

例题最大流的标号法精品文档例题最大流的标号法例2用标号法求下图所示的公路交通网络的最大流量 (要求写出标号过程并说明得到的的确是最大流)，其中，弧旁的数字是(c「f Q。

.⑴首先,给V s标上(0, )(2)检查V s，给V s为起点的未饱和弧的未标号的终点V2标号(V s, l(V2)),其中l(V2)min [l(V s),C s2 f s2】min[ ,15 7] 8其它点不符合标号条件。

⑶检查V2，给V2为终点的非零流弧的未标号的起点V3标号(V2, |(V3)),其中l(V3)min[g), f32】min[ 8,4] 4其它点不符合标号条件。

(4)检查v3，给v3为起点的未饱和弧的未标号的终点v4、v6标号(V4, l (V4)) > ( v6,l(V6))其中，l(V4)min[?3)234 ￡34] min[4,5 4] 1l(V6)min [l(V3),C36 f36] min [4,5 1] 4其它点不符合标号条件。

⑸检查v6，给v6为起点的未饱和弧的未标号的终点v t标号(v t, l (v t))其中，l(V t) mi n[l(V6), C6t f&] mi n[4,10 5] 4其它点不符合标号条件。

由于V t已标号，反向搜索可得增广链{(V s,V2),(V3,V2),(V3,V6),(V6,Vj}，在该增广链的前相弧(v s, v2), (v3, v6), (v6,v t)上增加l (v t) 4，在后向弧(v3, v2)上减去精品文档l(V t) 4，其它弧上的流量不变，则可得一流量v(f ) 20的新的可行流如下图重新开始标号：⑹首先,给V s标上(0, )(7)检查V s，给V s为起点的未饱和弧的未标号的终点V2标号(V s, l(V2)),其中l(V2) min [l(V s),C s2 f s2】 min[ ,15 11] 4其它点不符合标号条件。

最大流问题标号法例题详解最大流问题标号法例题详解本文以一道标号法求解最大流问题的例题胶加以详细讲解，帮助读者了解其原理及运算步骤。

题目如下：给定一个网络结构如下：s (源点) 0----1----2----3----4---- t (汇点)a 25 10 12 15 20其中 s 是源点，t是汇点，aij（i,j=0,1,2,3,4)是每条弧的容量，求整个网络的最大流量。

解：1、设置标号：在最大流问题中，为了求解最大流，最常用的方法是标号法。

首先，要设置各结点标号，因为本题中有5个结点，s源点的标号为0，t汇点标号为4，其他结点即1，2，3依次标号，标号的设定不仅便于求解，而且可以在初始化的时候使用。

2、初始化标号：初始化标号即将各结点初始化为两个空集合{}，即各结点的访问和未访问标号都是空集合，即无访问的结点标号为{}，访问过的结点标号也为{}。

3、依据标号法，从源点(s=0)计算，得出每条弧的剩余容量Cij，具体推导如下：源点0 1 2 3 41 0 25 10 12 152 0 0 10 7 103 0 0 0 8 104 0 0 0 0 20其中：Cij=aij-fij (i,j=0,1,2,3,4)其中，aij 为每条弧的容量，fij 为每条弧的流量，在初始情况下，fij=0，故Cij=aij。

4、找增广路径：从源点s开始，用深度优先搜索法查找从s到t的增广路径，具体步骤如下：设置一个数组P[i]用以记录路径，P[i]表示从s到i节点所经过的上一个结点，先从源点s开始，P[0]=-1，然后查找s出发可以到达的结点，若Cij>0，则有路可达，将P[j]=i（j为s出发可达的结点），接着查找j出发可以到达的结点（该结点未被访问过）若Cjk>0，则有路可达，把P[k]=j，以此类推，直到找到P[t]=-1，即从s到t 的一条增广路径找到，这条增广路径的路径上的容量称为Cmin，它是该增广路径上各结点之间的容量最小值。

第七章Operational厂§ 4网络最大流问题网络最大流冋题是网络的另一个基本冋题。

许多系统包含了流量问题。

例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。

许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。

4.1基本概念与定理1. 1.网络与流定义14 （1）网络：例1如图7-20是连结某产品产地’和销地一的交通图。

弧:1 表示从二到匚的运输线，弧旁的数字表示这条运输线的最大通过能力，.，括号内的数字表示该弧上的实际流一［。

现要求制定一个运输方案，使从一运到尸，的产品数量最多。

可行流与最大流输网络的实际问题中，我们可以看出，对于流有两个基本要求：一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力(即该弧的容量)二是起点发出的流的总和(称为流量)，必须等于终点接收的流的总和，且各中间点流 入的流量之和必须等于从该点流出的流量之和， 即流入的流量之和与流出的流量之和的差为 零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。

因此有下面所谓的可行流的定义。

定义14对于给定的网络 D=(V,A,C )和给定的流 』」：.「，若「满足下 列条件:(1)容量限制条件：对每一条弧 .-，有- -(7.9)(2)平衡条件： 对于中间点：流出量=流入量，即对于每一个对于出发带点T ：，有SA -'K/)对于收点①，有 工二 'I(7.12)则称/ - ■为一个可行流，•-称为这个可行流的 流量。

注意，我们这里所说的出发点 r 是指只有从匚发出去的弧，而没有指向J 的弧;收点二是指只有弧指向--，而没有从它的发出去的弧。

在运i (i 丰 s,t)，有(7.10)(7.11)可行流总是存在的。

例如令所有弧上的流，就得到一个可行流，（称为零流）,其流量 ': 一。

如图7-20中，每条弧上括号内的数字给出的就是一个可行流 3 - f/yJ ，它显然满足定义中的条件（1 ）和（2）。

最⼤流问题的⼏种经典解法综述⼀、什么是最⼤流问题假设现在有⼀个地下⽔管道⽹络，有m根管道，n个管道交叉点，现在⾃来⽔⼚位于其中⼀个点，向⽹络中输⽔，隔壁⽼王在另外⼀个点接⽔，已知由于管道修建的年代不同，有的管道能承受的⽔流量较⼤，有的较⼩，现在求在⾃来⽔⼚输⼊的⽔不限的情况下，隔壁⽼王能接到的⽔的最⼤值？为解决该问题，可以将输⽔⽹络抽象成⼀个联通的有向图，每根管道是⼀条边，交叉点为⼀个结点，从u流向v的管道能承受的最⼤流量称为容量，设为cap[u][v]，⽽该管道实际流过的流量设为flow[u][v]，⾃来⽔⼚称为源点s，隔壁⽼王家称为汇点t，则该问题求的是最终流⼊汇点的总流量flow的最⼤值。

⼆、思路分析关于最⼤流问题的解法⼤致分为两类：增⼴路算法和预流推进算法。

增⼴路算法的特点是代码量⼩，适⽤范围⼴，因此⼴受欢迎；⽽预流推进算法代码量⽐较⼤，经常达到200+⾏，但运⾏效率略⾼，如果腹⿊的出题⼈要卡掉⼤多数⼈的code，那么预流推进则成为唯⼀的选择。

( ⊙ o ⊙ )咳咳。

先来看下增⼴路算法：为了便于理解，先引⼊⼀个引理：最⼤流最⼩割定理。

在⼀个连通图中，如果删掉若⼲条边，使图不联通，则称这些边为此图的⼀个割集。

在这些割集中流量和最⼩的⼀个称为最⼩割。

最⼤流最⼩割定理：⼀个图的最⼤流等于最⼩割。

⼤开脑洞⼀下，发现此结论显⽽易见，故略去证明（其实严格的证明反⽽不太好写，但是很容易看出结论是对的，是吧）。

这便是增⼴路算法的理论基础。

在图上从s到t引⼀条路径，给路径输⼊流flow，如果此flow使得该路径上某条边容量饱和，则称此路径为⼀条增⼴路。

增⼴路算法的基本思路是在图中不断找增⼴路并累加在flow中，直到找不到增⼴路为⽌，此时的flow即是最⼤流。

可以看出，此算法其实就是在构造最⼩割。

增⼴路算法⽽预流推进算法的思路⽐较奇葩（没找到⽐较好的图，只能⾃⾏脑补⼀下了。

= =#）：先将s相连的边流⾄饱和，这种边饱和的结点称为活动点，将这些活动点加⼊队列，每次从中取出⼀个点u,如果存在⼀个相邻点v是⾮活动点，则顺着边u->v 推流，直到u变为⾮活动点。