给定一个有向图D=(V,A),在V中指定一点称为发点(记为 )，该点只有出发去的弧，指定另一点称为收点(记为，)，该点只有指向它的弧，其余的点叫做中间点。对于A中的
每一条弧W f,对应一个数*亠20(简记片)，称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。
(2)网络流：在弧集A上定义一个非负函数y_ (Z(Pl JV P)是通过弧
的实际流量，简记匚，称扌是网络上的流函数，简称网络流或流，称计Q为网络流的流量。
■ ?~ "
?丄 / √ 第七章
F?wearch ι
§ 4网络最大流问题
网络最大流冋题是网络的另一个基本冋题。
许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信
息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。
4.1基本概念与定理
1. 1.网络与流
定义14 (1)网络：
例1如图7-20是连结某产品产地二和销地一的交通图。弧∣∕Λ√<.;表示从二到的运输线，弧旁的数字表示这条运输线的最大通过能力IL ,括号内的数字表示该弧上的实际
流一］。现要求制定一个运输方案，使从-r运到甘t的产品数量最多。
可行流与最大流
4⑴
5(3)
IO （I ）
输网络的实际问题中，我们可以看出，对于流有两个基本要求
：
一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）
二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流 入的流量之和必须等于从该点流出的流量之和， 即流入的流量之和与流出的流量之和的差为 零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。
因此有下面所谓的可行流的定义。
定义14对于给定的网络 D= （ V,A,C ）和给定的流 ."H ■...， 若一.满足下列
条件：
（1） 容量限制条件：对每一条弧
工宀L ,有
(7.9)
（2）平衡条件： 对于中间点：
流出量=流入量，即对于每一个
i （i ≠ s,t ）,有
(7.10)
对于出发带点二，有
∑Λ ■
J l ）
对于收点■■-，有
⑺12)
则称」
_'；丨为一个可行流，’.丄 称为这个可行流的 流量。
注意，我们这里所说的出发点 I 是指只有从二发出去的弧，而没有指向「的弧；收
点二是指只有弧指向V.，而没有从它的发出去的弧。
在运
(7.11)
可行流总是存在的。例如令所有弧上的流J1. ,就得到一个可行流，（称为零流）, 其流量.I : 一。
如图7-20中，每条弧上括号内的数字给出的就是一个可行流/ = UJ ,它显然满足定义中的条件（1）和（2）。其流量v（7）= 5+3 = 8 O
所谓网络最大流问题就是求一个流」；_?： .,使得总流量达到最大，并且满足定
义15中的条件（1）和（2）,即
⑺13)
网络最大流问题是一个特殊的线性规划问题。我们将会看到利用图的特点，解决这个问题的方法较直线性规划的一般方法要简便和直观的多。
例2写出图7-20所表示的网络最大流问题的线性规划模型。
解设< I,则其线性规划模型为
max1 l.
Z3-Λ?-/M-Λ? 二0 仏+fy -儿-九-几=0
Λ? + Λ6-∕? = 0
Λ+‰ ÷∕? = V(Z)
j ≠ ff,t f(7 14)
牙人~~ 丁JE二* ?
在网络D=(V,A,C)中，若给定一个可行流J ；...,我们把网络中使的弧称为饱和弧，使θ≤Λ
如图7-20中的弧都是非饱和弧，而弧A八J为零流弧。
若"是网络中联结发点和收点匕的一条链，我定义链的方向是从I r到一则链上
S
的弧被分为两：
一类是：弧的方向与链的方向一致，我们称此类和为前向弧，所有前向弧的集合记
为.J。
另一类是：弧的方向与链的方向一致，我们称此类弧为后向弧，所有后向弧的集合
记为,。
如图7-20中，设
/■'. "√,.. J ''j? - \ - : Il L 1.〕是一条从儿到V 的链，
则
J 'j> 3 1：■ ：' ：1 . , ■- ^r-?v√-'
定义15设匚A-是网络D=(V ,A,C)上的一个可行流，门是从二到匕的一条链，若门满足下列条件：
(1)在弧\ - J - . J (V i,V j) ∈μ+上，即.」J中的每一条弧都是非饱和弧；
⑵在弧■丄上，即」中的每一条弧都是非零流弧。
则称尸是关于J的一条增广链。
如前面所说的链就是一条增广链。因为其中μ+上的弧均非饱和，如(V s,V2) ∈μ
+ ,f s2=5
4.截集与截量
定义16给定网络D=(V ,A,C)，若点集V被分割成两个非空集合V1和V2,使得
V=V 1+V2,V1 ∩ V2=φ(空集)，且V s ∈V1,v t∈V2，则把始点在V1,终点在V 2的弧的集合称为分离V S和V t的一个截集，记为(V 1,V2)o
如图9.26 中，设V1= {V s,v2,v5}, V 2= {v3,v4,V6,vJ 则截集为
"?- V 1 '. —I ,
而弧(v3,V2)和(V4,V5)不是该集中的弧。因为这两条弧的起点在V2中，与定义17不符。
显然，一个网络的截集是很多的(但只有有限个) ，例如在图7-20中，还可以取
叫-—?I，二：「，则截集为
另外，若把网络D=(VAC)中某截集的弧从网络D中去掉，则从V S到V t便不存在路，所以
直观上说，截集是从V S到V t的必经之路。
定义17在网络D=(V ,A,C)中，给定一个截集(V1,V2)，则把该截集中所有弧的容量之和，称为这个截集的容量，简称为截量，记为c(V1,V2),即
C(Vι,V2)=二二(7.16)
叫?他
例如在上面我们所举的两个截集中，有
Λ)=?+? +? =9+6+9 = 24
而
= r j3÷c24+ c15= 9 + 6÷5 = 20
显然，截集不同，其截量也不同。由于截集的个数是有限的，故其中必有一个截集的容量是最小的，称为最小截集，也就是通常所说的“瓶颈”
不难证明，网络D=(V ,A,C)中，任何一个可行流f= {f j}的流量V(f),都不会超过任—
截集的容量，即
v( f ) ≤C (V1,V2) (7.17) 如果存在一个可行流f*= {f*j},网络D=(V,A,C)中有一个截集(％：町)，使得
' (7.18)
则八: 必是最大流，而(W) 必是D中的最小截集。为了求网络最大流f*,我们也说明下面的重要定理。
*定理4在网络D=(V ,A,C)中，可行流f 二忧}是最大流的充要条件是D中不存在关
于f*的增广链。
证先证必要性。用反证法。若f*是最大流，假设D中存在着关于f*的增广链μ,令
(7.19)
由增广链的定义可知θ>0 ,令
(7.20)
不难验证」"是一个可行流，且有
这与f*是最大流的假定矛盾。
、、 * * *
再证充分性：即证明设D中不存在关于f的增广链，f是最大流。
用下面的方法定义：令-八"
若WL ,且有7-.. ■< <■ ■，则令「一：；
若L f ,且有、D ,则令YL ［。
因为不存在着关于」J的增广链，故「「
记-J i - I1P,于是得到一个截集(V*,/)。显然有
所以V(f )=c I ∣'.，于是f必是最大流。定理得证。
由上述证明中可见，若「'是最大流，则网络必定存在一个截集使得(7.18)
式成立。
7定理5 (最大流一一最小截集定理)对于任意给定的网络D=(V ,A,C),从出发点VS到
收点Vt的最大流的流量必等于分割I和二的最小截集V的容量，即
VG re)= (Pix)
由定理4可知，若给定一个可行流「' . ■/ ',只要判断网络D有无关于/'：'的增
广链。如果有增广链，则可以按定理4前半部分证明中的办法，由公式(7.19)求出调整量Q, 再按式(7.20)的方法求出新的可行流。如果流有增广链，则得到最大流。而根据定理4后
半部分证明中定义的办法，可以根据Vt是否属于来判断D中有无关于f的增广链。
在实际计算时，我们是用给顶点标号的方法来定义的，在标号过程中，有标号的顶点表示是? 1中的点，没有标号的点表示不是「中的点。一旦有了标号，就表明找到一条
从V S到V t的增广链；如果标号过程无法进行下去，而V t尚未标号，则说明不存在从V S到V t
的增广链，于是得到最大流。这时将已标号的点（至少有一个点V S）放在集合！中，将未
标号点（至少有一个点V t）放在集合中，就得到一个最小截集。
4.2 寻求最大流的标号法（FOrd , FUIkerSOn）
从一个可行流出发「Γ（若网络中没有给定Li ,则可以设’是零流），经过标号
过程与调整过程。
1）1）标号过程
在这个过程中，网络中的点或者是标号点（又分为已检查和未检查两种），或者是未标
号点，每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找
出增广链；第二个标号是为确定增广链的调整量θ用的。
标号过程开始，总先给V S标上（0,+ ∞）,这时V S是标号而未检查的点，其余都是未标号
点，一般地，取一个标号而未检查的点V i，对一切未标号点V j:
（1）在弧上S .打，孕，则给V j标号一「】.。这里＞：■'.■ I：.-：. 一，。这
时点V j成为标号而未检查的点。
（2）若在弧［上，［「，给V j标号丄小。这里-:'：'°这时点
V j成为标号而未检查的点。
于是一成为标号而已检查过的点，重复上述步骤，一旦一被标上号，表明得到一条从
到-的增广链-,转入调整过程。
若所有标号都是已检查过，而标号过程进行不下去时，则算法结束，这时的可行流就是
最大流。
2）2调整过程
首先按★及其它点的第一个标号，利用“反向追踪”的办法，找出增广链μ。例如设
V t的第一个标号为咗（或呢），则弧（V il V J）（或相应地（VJ）是μ上的弧。接下来检查U的第一个标号，若为
（或），则找出何J ifc）（或相应地（V tr V J））°再检查勺的
第一个标号，依此下去，直到I为止。这时被找出的弧就构成了增广链H。令调整量θ是,即二的第二个标号。
几?+&?√
令A' j甘-R(V in V J.) (=j LT^
去掉所有的标号，对新的可行流,重新进入标号过程。
下面，以例题说明此算法求解过程。
例3用标号法求图7-20所示网络最大流。弧旁的数是I■:
解对图7-20中各顶点进行标号。
首先给y标(0,+ ∞),即Z )
检查:
在弧：K -C il上,因为?[,_ ?[一，又有
.，■】_；- H '[ ■ ., ：■..'ι.j in 「；I :,所以给二标'；：■'；
在弧上J，因为?：?-_,又有
■' 1 . 1 11 ' U- ■X l',所以给二标 1 ,' l^?。
检查二:
在弧上：飞“：；，因为J打-，又有
V ?_」—「* I' ；「一「」二所以给标：■'! ■.；
在弧上「，.，因为一；H ?'討，又有
—厂1，_ _ ,所以给二标匸；
在弧：二讥[上，因为?[_ -',又有
'■ ??l■「’I，= ' 11 '.l',所以给V3 标.。
因为前面已给V3标过号I ■ ■ I，这里又给二标. '),它们分别表示两条不同的路线，
这里不存在修改标号的问题(与最短路不同) 。因为我们的目标是尽快找出一条从VS到Vt 的增广链，即尽快使终点Vt获得标号，所以不必在中途过多停留。也就是说在对已标号点
Vi进行检查时，每次只检查一个相邻点Vj (不论前向弧或后向弧均可)，再给标号即可，而不必检查所有与Vi相邻的点。事实上，其余的相邻点也不会漏掉，因为以后还要通过检查这些点来找出新的增广链。以下我们就按这种思路进行。
检查：V J
在弧I ：一…：上，因为「-,，又有
:L. I i I ■' ■ J I L l I' I ■，： - 「.所以给一标「二.
至此，终点二已获得标号，于是找出一条I从到厶的增广链。再由标号的第一部分用反向追踪法找出路线，即
? = f叫巴宀弋}
j
（见图7-21 ）。
进行调查：
这时的调整量-.再按公式（7.20）调整。由于」N上各弧均为前向弧，故得
''-< -，
匕-二「；-「^，
（见图7-21）.其余的j」不变.
对这个新的可行流再进入标号过程，寻找新增广链。开始给标：.「「「，检查丁”，
给二标律—，检查门:
在弧（叫上，因为&站二匚J（见图7-21），故该弧已饱和，标号无法进行下去。
在弧√上，因为_,討?■討，又有
/（v4）= min {∕（v5）Λ2+-A4} = min（3 } = 3
所以给H标訂:
?(? f B)
vβ(0Λ∞)
在弧他亠）上’因为儿V气「
又有
血）=≡1 P（V J）,? ■ ΛJ = min {?5 - 2] = 3
所以给匕标上."j
检查V :
在弧〔匕、）上，因为丄?.,,又有
I ：I I1I-' - .,√ ! Il 「，所以给二标匚：；.
于是又得到一条增广链宀：—J. ..?.√. f I （见图7-22）
进行调整：这时
二I ：:。调整结果如图9.28所示。再重新标号求新的增广链.
开始给二标I l?T? ,检查一，给标九。检查R ,给L l Z标L ：,检查J ，给匕标W：」），检查昨，因（叫已是饱和弧（见图7-22）。标号无法进行。
但在弧上，代?I ?又有
1 1 b；“—人.. 1- ,所以给二标I l I：.
于是又得到一条增广链：
再进行调整（见图7-23）.
V- . .
再重新进行标号求新开始给匕标（0, +8）,检查巴，给匕标时」）.
检查二：
这时弧均已饱和。而在弧■. √,. I 上,因?' ■-,又有
I . .1 I ' 1. II ^. I ■所以给门标宀,表明弧 > , 为后向弧.
检查匕，给「4标.1■ ■。检查二，给―标?,∣ O于是又得到一条增广链:
再重新进行开始给标（0,+ ∞）,检查二，给二标。检查儿，这时.v-'.I和?一 .斗.均为前向弧，都已饱和，弧■:为后向弧，且为零流弧〔“-’；。故标号无法进行。但在弧
-:上因为L ?j.—。又有
'I1：| I '；■'：. ., . -L'.. Ii 」八一一 ^ .所以给 7 标；厂..
检查匕,给：.标〕L二。检查τ.,因为> .■已饱和（见图7-24）。而在弧1'- r 上，因为.-4C I - ■'，：，又有
' J. H口一_.* I I- 所以给二标■'■■■.\> ,再检查一，给一标上.。于是又得到一条增广链：
j-. .?..? I- ■:- .■.
再进行调整（见图7-25 ）。
再重新进行标号求新的增广链。
开始给「：标（0,+ ∞
I上标号还可以继
续进行，给―标-；「。检查二。给―标''.；■: o于是又得到一条增广链
?二｛叫巴「％气｝
再进行调整（见图7-26 ）。
再重新进行标号:
开始给】\：标（0,+ ∞），检查:这时弧已饱和。标号无法进行。而:还可以标
再检查】匕，如前所述，标号也无法进行。
至此已求得最大流。我们将最大流：? - I []表示在图7-27中。最大流量为vσt)=z>∕>x÷Λ>X=20
与此同时，可找到最小截集」??.t I，其中T为最后一轮已标号点的集合，I:为未标号点的集合，即
卩；二他七｝, 述二何M巴宀
(J r↑Λ*) = ｛〔叫，V B ? (V a ^t),(v j,v i))
最小截量为
= ?÷?÷^a3= 9 + ^÷5= 20
由上述可见，用标号法找增广链以求最大流的结果，同时也得到一个最小截集。最小
截集的容量的大小影响总的运输量的提高。因此，为提高总的运输量，必须首先考虑增大最
小截集中各弧的容量，提高它们的通过能力。反之，一旦最小截集中弧的通过能力降低，必
然会使得运输量减少。
前面讨论都是对一个发点、一个收点的网络最大流问题。对于多个发点和收点的情形，
我们可以采取虚设一个总发点二和总收点一，从总发点到各发点；：均以弧相联，并且
令这些弧的容量均为∞或某一具体值（根据情况而定）。同样，从各个收点到总收点二亦
以弧相联，也令这些弧的容量为∞或某一具体值。这样，原来的发点V z与收点二都变成了
转运点，原来的问题就转变成一个发点一个收点的网络图。例如图7-28所示是两个发点两
个收点的网络，可以转换成一个发点一个收点的网络，见图7-29所示。
C ----------- ——
［第一节］［第二
节］
［第三节］［第四
节］
［返
回］
给定一个有向图D=(V,A),在V中指定一点称为发点(记为),该点只有出发去的弧,指定另一点称为收点(记为),该点只有指向它的弧,其余的点叫做中间点。对于A中的每一条弧,对应一个数(简记),称之为弧的容量。通常我们把这样的D叫做网络,记为D=(V,A,C)。 (2)网络流:在弧集A上定义一个非负函数。就是通过弧 的实际流量,简记,称就是网络上的流函数,简称网络流或流,称为网络流的流量。 §4 网络最大流问题 网络最大流问题就是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量,金融系统有现金流,控制系统有信息流等。许多流问题主要就是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4、1 基本概念与定理 1．1.网络与流 定义14 (1)网络: 例1如图7-20就是连结某产品产地与销地的交通图。弧表示从 到的运输线,弧旁的数字表示这条运输线的最大通过能力,括号内的数字表示该弧上的实际流。现要求制定一个运输方案,使从运到的产品数量最多。 可行流与最大流 在运输网络的实际问题中,我们可以瞧出,对于流有两个基本要求:
一就是每条弧上的流量必须就是非负的且不能超过该弧的最大通过能力(即该弧的容量); 二就是起点发出的流的总与(称为流量),必须等于终点接收的流的总与,且各中间点流入的流量之与必须等于从该点流出的流量之与,即流入的流量之与与流出的流量之与的差为零,也就就是说各中间点只起转运作用,它既不产出新的物资,也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=(V,A,C)与给定的流,若满足下列条件: （1）容量限制条件:对每一条弧,有 (7、9) (2)平衡条件: 对于中间点: 流出量=流入量,即对于每一个i (i≠s,t),有 (7、10) 对于出发带点,有 (7、11) 对于收点,有 (7、12) 则称为一个可行流,称为这个可行流的流量。 注意,我们这里所说的出发点就是指只有从发出去的弧,而没有指向的弧;收点就是指只有弧指向,而没有从它的发出去的弧。 可行流总就是存在的。例如令所有弧上的流,就得到一个可行流,(称为零流),其流量。 如图7-20中,每条弧上括号内的数字给出的就就是一个可行流,它显然满足定义中的条件(1)与(2)。其流量。 所谓网络最大流问题就就是求一个流,使得总流量达到最大,并且满足定义15中的条件(1)与(2),即 max
给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从 到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的产品数量最多。 可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。 注意，我们这里所说的出发点是指只有从发出去的弧，而没有指向的弧； 收点是指只有弧指向，而没有从它的发出去的弧。
最大流问题 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。 网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。 基本概念 设一个赋权有向图D=(V , A)，在V 中指定一个发点（源）vs 和一个收点（汇）vt ，且只能有一个发点vs 和一个收点vt 。（即D 中与vs 相关联的弧只能以 vs 为起点，与vt 相关联的弧只能以 vt 为终点），其他的点叫做中间点。 对于D 中的每一个弧(vi, vj)A ∈，都有一个权cij 叫做弧的容量。我们把这样的图 D 叫做一个网络系统，简称网络，记做D =(V , A, C) 。 Vs Vt 图1 图1是一个网络。每一个弧旁边的权就是对应的容量。 网络D 上的流，是指定义在弧集合A 上的一个函数f={f(vi, vj)}={fij}，f(vi,vj)=fij 叫做弧在(vi,vj)上的流量 。 Vs Vt 图2 图2中，每条弧上都有流量fij ，例如fs1=5，fs2=3，f13=2等。 容量是最大通过能力，流量是单位时间的实际通过量。显然，0≤fij≤cij 。网络系统上流的特点： (1)发点的总流出量和收点的总流入量必相等； (2)每一个中间点的流入量与流出量的代数和等于零； (3)每一个弧上的流量不能超过它的最大通过能力（即容量）。网络上的一个流f={fij}叫做可行流，如果f 满足以下条件： （1）容量条件：对于每一个弧(vi,vj)A ∈，有0≤fij≤cij 。
（2）平衡条件： 对于发点vs ，有∑f sj ?∑f js =v (f ) 对于收点vt ，有∑f tj ?∑f jt =?v (f ) 对于中间点，有∑f ij ?∑f ji =0 其中发点的总流量（或收点的总流量）v(f)叫做这个可行流的流量。 网络系统中最大流问题就是，在给定的网络上寻求一个可行流f={fij}，其流量v(f)达到最大值，即从vs 到vt 的通过量最大。 最大流问题可以通过线性规划数学模型来求解。图1的最大流问题的线性规划数学模型为 max v =f s 1+f s 2 s.t. { ∑j f ij ?∑i f ij =0 i ≠s,t 0≤f ij ≤c ij 所有弧(v i ,v j ) fs1和fs2是与起点相连的两条弧上的流量。 满足上式的约束条件的解{fij}称为可行解，在最大流问题中称为可行流。 对有多个发点和多个收点的网络，可以另外虚设一个总发点和一个总收点，并将其分别 与各发点、收点连起来，就可以转换为只含一个发点和一个收点的网络。 S T 所以一般只研究具有一个发点和一个收点的网络。 我们把fij=cij 的弧叫做饱和弧，fij
从一道题目的解法试谈网络流的构造与算法 福建师大附中江鹏 1. 引论 A. 对网络流算法的认识 网络流算法是一种高效实用的算法，相对于其它图论算法来说，模型更加复杂，编程复杂度也更高，但是它综合了图论中的其它一些算法（如最短路径），因而适用范围也更广，经常能够很好地解决一些搜索与动态规划无法解决的，看似NP的问题。 B. 具体问题的应用 网络流在具体问题中的应用，最具挑战性的部分是模型的构造。这没用现成的模式可以套用，需要对各种网络流的性质了如指掌（比如点有容量、容量有上下限、多重边等等），并且归纳总结一些经验，发挥我们的创造性。
2. 例题分析 【问题1】项目发展规划（Develop） Macrosoft?公司准备制定一份未来的发展规划。公司各部门提出的发展项目汇总成了一张规划表，该表包含了许多项目。对于每个项目，规划表中都给出了它所需的投资或预计的盈利。由于某些项目的实施必须依赖于其它项目的开发成果，所以如果要实施这个项目的话，它所依赖的项目也是必不可少的。现在请你担任Macrosoft?公司的总裁，从这些项目中挑选出一部分，使你的公司获得最大的净利润。 ●输入 输入文件包括项目的数量N，每个项目的预算Ci和它所依赖的项目集合Pi。格式如下：第1行是N； 接下来的第i行每行表示第i个项目的信息。每行的第一个数是Ci，正数表示盈利，负数表示投资。剩下的数是项目i所依赖的项目的编号。 每行相邻的两个数之间用一个或多个空格隔开。 ●输出 第1行是公司的最大净利润。接着是获得最大净利润的项目选择方案。若有多个方案，则输出挑选项目最少的一个方案。每行一个数，表示选择的项目的编号，所有项目按从小到大的顺序输出。 ●数据限制 0≤Ｎ≤1000 -1000000≤Ci≤1000000 ●输入输出范例
开题报告 数学与应用数学 网络最大流问题算法研究 一、综述本课题国内外研究动态, 说明选题的依据和意义 最大流问题是指在一定的条件下, 要求流过网络的物流、能量流、信息流等流量为最大的问题[2]. 最大流问题已有50多年的研究历史, 这段时期内, 人们建立了最大流问题较 为完善的理论, 同时开发了大量优秀的算法. 如Ford 和Fulkerson 增截轨算法 [3]、Dinic 阻塞流算法、Goldberg 推进和重标号算法[6]以及Goldberg 和Rao 的二分长度阻塞流算法等等, 这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用. 近年来, 随着计算机科学技术和网络的快速发展, 网络最大流问题得到了更深入的研究, 并极大地推动了最大流问题的研究进展. 然而, 研究工作仍未结束: 首先, 在理论算法研究方面, 人们还没有发现最大流问题算法时间复杂度的精确下界, 更没有任何一个通用算法达到或接近问题的下界; 其次, 在算法的实际性能方面, 目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决, 发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决. 因此, 关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig 提出的网络单纯刑法和Ford 和Fulkerson 的增载轨算法, 他们都是伪多项式时间算法, 分别由Dinic, Edmonds 和Karp 等提出. 1973年Dinic 首次获得了时间复杂度的核心因子为nm 算法. 以后的几十年中, 最大流算法获得了很大的进展. 在最大流问题中, ()nm O 时间界是一个自然的障碍. 如果我们把一个流沿从源到汇的各个路径进行分解, 根据流分解定理, 这些包含流的路径的总长度为()nm Θ.因此, 对每次利用一条曾接轨的算法, ()nm O 时间是这类算法的下界. 尽管这个下界对使用动态树数据结构或基于预流概念的算法是不适用的, 但在很长一段时间内, ()nm O 的
文献综述 数学与应用数学 网络最大流问题算法研究 最大流问题是指在一定的条件下,要求流过网络的物流、能量流、信息流等流量为最大的问题[2].最大流问题已有50多年的研究历史,这段时期内,人们建立了最大流问题较为完善的理论,同时开发了大量的算法.如Ford和Fulkerson增截轨算法、Dinic阻塞流算法、Goldberg推进和重标号算法[6]以及Goldberg和Rao的二分长度阻塞流算法等等,这些经典算法及相关技术对网络最大流问题的研究起到了非常重要的推动作用.近年来,随着计算机科学技术和网络的快速发展,网络最大流问题得到了更深入的研究,并极大地推动了最大流问题的研究进展.然而,研究工作仍未结束:首先,在理论算法研究方面,人们还没有发现最大流问题算法时间复杂度的精确下界,更没有任何一个通用算法达到或接近问题的下界; 其次,在算法的实际性能方面,目前算法的实际性能也不能满足许多应用问题的要求; 同时,最大流问题作为特殊的线性规划问题, 它远比一般线性规划问题容易解决,发现应用领域中的问题和最大流问题的联系可以使应用问题更好地得到解决.因此,关于网络最大流问题的研究具有十分重要的理论意义和实用价值[5]. 最早的算法是Dantzig[6]提出的网络单纯刑法和Ford和Fulkerson的增载轨算法, 他们都是伪多项式时间算法,分别由Dinic、Edmonds和Karp等提出.1973年Dinic首 次获得了时间复杂度的核心因子为nm算法.以后的几十年中,最大流算法获得了很 大的进展. 本文主要介绍的是网络最大流的几种主要算法,其中重点介绍了标号算法的详细 过程,其后给出了其在实际中的应用实例,后面介绍了现有的几种主要算法,虽然没 有给出具体的程序,但本文目的主要是了解最大流问题的解决思想,读者对网络流算 法有更深刻的认识,读者要想了解更多关于最大流问题的研究,详细可以参照Goldberg等人的研究成果, 这些程序在网上都可以轻松得到. 在这里就不再详细讲述. 下面简要介绍一下增载轨算法. 增载轨算法[5]: 沿剩余网络中从源到汇的有向路径推进流. 增载轨算法包括Ford
网络最大流问题
给定一个有向图D=(V,A)，在V中指定一点称为发点（记为），该点只有出发去的弧，指定另一点称为收点（记为），该点只有指向它的弧，其余的点叫做中间点。对于A中的每一条弧，对应一个数（简记），称之为弧的容量。通常我们把这样的D叫做网络，记为D=(V,A,C)。 （2）网络流：在弧集A上定义一个非负函数。是通过弧的实际流量，简记，称是网络上的流函数，简称网络流或流，称为网络流的流量。 §4 网络最大流问题 网络最大流问题是网络的另一个基本问题。 许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 4.1 基本概念与定理 1．1．网络与流 定义14 （1）网络： 例1如图7-20是连结某产品产地和销地的交通图。弧表示从到的运输线，弧旁的数字表示这条运输线的最大通过能力，括号内的数字表示该弧上的实际流。现要求制定一个运输方案，使从运到的 产品数量最多。 可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个基本要求： 一是每条弧上的流量必须是非负的且不能超过该弧的最大通过能力（即该弧的容量）； 二是起点发出的流的总和（称为流量），必须等于终点接收的流的总和，且各中间点流入的流量之和必须等于从该点流出的流量之和，即流入的流量之和与流出的流量之和的差为零，也就是说各中间点只起转运作用，它既不产出新的物资，也不得截留过境的物资。 因此有下面所谓的可行流的定义。 定义14对于给定的网络D=（V,A,C）和给定的流，若满足下列条件： （1）容量限制条件：对每一条弧，有 (7.9) （2）平衡条件： 对于中间点： 流出量=流入量，即对于每一个i (i≠s,t)，有 (7.10) 对于出发带点，有 (7.11) 对于收点，有 (7.12) 则称为一个可行流，称为这个可行流的流量。
云南大学数学与统计学实验教学中心 实 验 报 告 一、实验目的 编制程序，在赋权图中找到从发点Vs 到收点Vt 的最大流，并输出最大流. 二、实验环境 VS2010（C++） 三、实验内容 P272 例14： 用标号法求图10-25所示网络的最大流，弧旁的数是()ij ij f c , 四、实验过程 A 、将上面算法编写实现运行结果如下图： 用标号法寻找网络中最大流的基本思想是寻找可增广链，使网络的流量得以增加， 直到最大为止（标号过程进行不下去，而收点vt 尚未标号，说明不存在增广路，得到最大流）。我采用的方法是从零流开始，再用标号法寻求最大流。 标号法主要分为两个步骤： (1) 标号过程 开始标号，初始化结点的结构体数组，然后标记vs 为标号点并进行检查，此时 其余都是未标号的点。然后找到与vs 有边相连的结点，标记那些点为标号而未检查的点。取一个标号而未检查(Tag=marking)的点vi ，对于一切未标号(Tag=n_mark) 的点vj ： A)．对于弧(vi ，vj)，若fij
到一条从vi到vt的增广路径p，转入调整过程。 若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。 (2) 调整过程 从vt点开始，通过每个点的第一个标号，反向追踪(根据结点的From信息)，可找出增广路P。直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算调整值：min{min(cij-fij)，min（fij）} a、初始化结果： 输入的结果为红色字体 b、初始化后的到结果： 红框中得到的图的关系与课本例题中的一样！所以创建图形正确！ c、最后得到的结果：