《网络流ppt.ppt》由会员分享，可在线阅读，更多相关《网络流ppt.ppt（87页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 网网 络络 流流 1 网络流理论的背景网络流理论的背景2 网络流的基本概念和结论网络流的基本概念和结论3 网络流的几个主要研究分支网络流的几个主要研究分支 3.1最大流最大流 3.2最小费用最大流最小费用最大流 4 发展前景发展前景目录目录 网络流是图论中一种理论和方法，研究网络上的一类最优化问题。T.E.哈里斯于1955年研究铁路网的最大通过能力时首先提出，在一个给定的网络上寻求某两点间的最大运输量问题。1956年，L.R.福特和D.R.富尔克森给出了算法，从而建立了网络流理论。1 网络流理论的背景网络流理论的背景 图论算法在信息学中扮演着相当重要的角色，它的分支之多、应用范围之广令所有其
2、它算法都望尘莫及。而网络流算法正是图论算法中的一个重要分支，它特点突出、作用显著，因此应用范围十分广范。下面主要讲网络流中的一些基本概念和结论，然后通过简单例子，阐述网络流算法的实现方法，对网络流算法作更深入、更彻底的认识。2 网络流的基本概念网络流的基本概念流量f(u,v)容量c(u,v)单边，多边增广路：可以增加流量的路残量网络：增广之后容量不为0的边构成的网络割最小割 设是定义在集合E上的非负函数。用ij表示在弧e=(i,j)上的函数值,并称为在弧e上从i到j的流量。若函数满足以下两个条件,则称函数为网络上的流,简称网络流：在每一条弧上，0ijcij0ijcij；平衡条件:当vi是中间点
3、时：f-(vi)=f+(vi)f-(vi)=f+(vi)式中 f+(vi)f+(vi)是对所有以i为起点的弧求和,f-(vi)f-(vi)是对所有以i为终点的弧求和。当vi是源点和终点时：f-(t)=f+(s)f-(t)=f+(s)，称为(在网络上)的流量。网络流网络流 如图1 中的a表示一个网络，箭头表示弧的方向,弧上的数表示容量。b、c表示网络a上的两个流，弧上的数字表示该弧的流量。b的流量为4，c的流量为5。例子 由网络中的点组成的序列 若对每一对相继点i、i+1或者(i,i+1)或者(i+1,i)是网络中的弧,则称p是一条连结0到k的通路通路。设p是一条连接s到t的链,从s出发，沿p走
4、到t时，则链p中与走向有相同方向的弧称为前向弧；有相反方向的称为后向弧。如果对于给定的流,它在p 的每条前向弧上的流量都小于容量，在每条后向弧上的流量都大于零，则称通路 p是关于流的一个增广路（链）增广路（链）。例如，在图1b中,ps,2,1,4,t是一个增广链。(s,2)、(4,t)是前向弧，其上的流量都小于容量；(1,2),(4,1)是后向弧，其上的流量都大于零。如果在此增广链的前向弧上，流量都增加1,后向弧上流量都减少1，就可从b变到c，从而使流量从4增加到5。增广路：增广路：割切：割切：G=(V,E,C)是已知的网络流图，设U是V的一个子集，W=V U，满足Vs W，Vt U。即W、U
5、把V分成两个不相交的集合，且源点和汇点分属不同的集合。对于弧尾在U，弧头在W的弧弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量割切的容量，记为C（U，W）.截集截集截集截集a:Ca=C01+C02+C0na:Ca=C01+C02+C0n割切a：v0v1，v0v2，v0vna的容量:Ca=C01+C02+C0n最小截集（割切）最大流定理：一个网络中，各种割切中容量最小的称为最小割切，用min C(U,W)表示。任一有向网络流，从发点到收点的最大流量任一有向网络流，从发点到收点的最大流量任一有向网络流，从发点到收点的最大流量任一有向网络流，从发点到收
6、点的最大流量Max Max f f 等于最小截集容量等于最小截集容量等于最小截集容量等于最小截集容量Min C(W,U)Min C(W,U)。即：即：即：即：Max f =Min C(W,U)Max f =Min C(W,U)图1的c是一个流量达到最大的流（流量为5），截集(s,1),(2,3,4,t)是一个最小截集（截量为5）。最小割容量最小割容量=最大流最大流 3.1最大流最大流 3.2最小费用最大流最小费用最大流 3 网络流的几个主要研究分支网络流的几个主要研究分支 在网络上寻求一个使流量()达到最大的流，称之为网络最大流问题。它是网络流理论中的一个主要研究课题,已获得一些重要结果：若各
7、弧上的容量都是正整数，则必存在各弧上的流量都是整数的最大流。流是最大流的充分必要条件是,不存在关于的增广链。从而将寻求最大流问题化为判断有无增广链问题。易见，图1中的b不是最大流。福特和富尔克森提出了一种标号法，即对网络上的点给以标号，从s出发沿网络上的弧向t探寻增广链的方法。最大流问题最大流问题:下面介绍一下最大流的几个主要算法。其思想大致如下：1 augment path“增广路”法1从任一已知流(如零流)开始，递推地构造一个其值不断增加的流的序列。2 在每一个新流构成之后，如果N有f的可增长链，则f不是最大流。3可得基于P的修改流f，并作为递增流序列的下一个流，如果不存在f 可增长链，则
8、f 是最大流，停止，否则重复。寻找增流路方法（标号法）：寻找增流路方法（标号法）：寻找增流路方法（标号法）：寻找增流路方法（标号法）：从v0开始，沿着边从已有标号vi出发，对符合下列条件之一相邻顶点vj作标记，直到vn；1 如(vi,vj)是前向弧，条件是 f(i,j)0 设设设设P=v0v1v2.vnP=v0v1v2.vn为网络中的一条通路，为网络中的一条通路，为网络中的一条通路，为网络中的一条通路，令令令令 (P)=min (P)=min (i,j)i,j)其中其中其中其中 (i,j)=Cij-fij (vi,vj)i,j)=Cij-fij (vi,vj)是前向弧是前向弧是前向弧是前向弧
9、fij (vi,vj)fij (vi,vj)是后向弧是后向弧是后向弧是后向弧其中Cij是边容量，f(i,j)是流过边 vivj 的可行流量，（f(i,j)Cij）定义：若(P)=0 称P为f 的饱和的；若(P)0 称P为f 的不饱和的。定义：一条从发点到收点的 f不饱和通路称为f 的增长道路（增流路）。在一个网络中，在一个网络中，在一个网络中，在一个网络中，f f 的的的的增长道路的存在表示增长道路的存在表示增长道路的存在表示增长道路的存在表示 f f 不是最大流。不是最大流。不是最大流。不是最大流。所以。沿着所以。沿着所以。沿着所以。沿着P P增加一个值为增加一个值为增加一个值为增加一个值为
10、 (P)(P)的附加流，得到一个的附加流，得到一个的附加流，得到一个的附加流，得到一个新流：新流：新流：新流：f(i,j)+f(i,j)+(P)(vi,vj)(P)(vi,vj)是前向弧是前向弧是前向弧是前向弧f1(i,jf1(i,j）=f(i,j)-=f(i,j)-(P)(vi,vj)(P)(vi,vj)是后向弧是后向弧是后向弧是后向弧 f(i,jf(i,j）其他其他其他其他定理：定理：定理：定理：当且仅当当且仅当当且仅当当且仅当N N中不包含中不包含中不包含中不包含 f f 增长道路时，增长道路时，增长道路时，增长道路时，N N中的流中的流中的流中的流 f f 是最大流。是最大流。是最大流
11、。是最大流。v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(0,5)(0,5)(0,5)(0,5)(0,6)(0,6)(0,10)(0,10)(0,6)(0,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(0,2)(0,2)(0,3)(0,3)(0,4)(0,4)例子例子（流值，容量）（流值，容量）v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(0,5)(0,5)(0,5)(0,5)(0,6)(0,6)(0,10)(0,10)(0
12、,6)(0,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(0,2)(0,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(0,5)(0,5)(0,5)(0,5)(0,6)(0,6)(0,10)(0,10)(0,6)(0,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(0,2)(0,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)
13、(0,5)(0,5)(0,5)(0,5)(0,6)(0,6)(0,10)(0,10)(0,6)(0,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(0,2)(0,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(0,5)(0,5)(0,5)(0,5)(0,6)(0,6)(0,10)(0,10)(0,6)(0,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(0,2)(0,2)(0,3)(0,3)(0,4)(0,4)增流路：增流路：v0v3v1v2
14、vn增流值增流值=2v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(2,5)(2,5)(0,5)(0,5)(2,6)(2,6)(0,10)(0,10)(2,6)(2,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(2,5)(2,5)(0,5)(0,5)(2,6)(2,6)(0,10)(0,10)(2,6)(2,6)(0,3)(
15、0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)增流路：增流路：v0v2vn增流值增流值=4v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(2,6)(2,6)(0,10)(0,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)f=6v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4
16、)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(2,6)(2,6)(0,10)(0,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(2,6)(2,6)(0,10)(0,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v
17、5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(2,6)(2,6)(0,10)(0,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(2,6)(2,6)(0,10)(0,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(
18、0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(0,10)(0,10)(0,4)(0,4)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(2,6)(2,6)(0,10)(0,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)增流路：增流路：v0v1v2v4vn增流值增流值=4v0v0v5v5v4v4v3v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(0,5)(0,5)(2,
19、5)(2,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)f =10v0v0v5v5v4v4v3
20、v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(0,5)(0,5)(2,5)(2,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)
21、(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)增流路：增流路：v0v3vn增流值增流值=3v0v0v5v5v4v4v3v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)f=13v0v0v5v5v4v4v3v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4
22、,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)f=13v0v0v5v5v4v4v3v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2
23、vnvn(4,10)(4,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)
24、(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(4,10)(4,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(4,10)(4,10)(6,6)(6,6)(0,3)(0,3)(0,3)(0,3)(0,3)(0,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)增流路：增流路：v0v1v5v4vn增流值增流值=3v0v0v5v5v4v4v3v3v1v1v2v2vnvn(7,10)(7,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6
25、,6)(6,6)(7,10)(7,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(7,10)(7,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(7,10)(7,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)f =16v0v0v5v5v4v4v3v3v1v1v2v2vnvn(7,10
26、)(7,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(7,10)(7,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(7,10)(7,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(7,10)(7,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(2,2)(2,2)(0,3)(0,3
27、)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(7,10)(7,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(7,10)(7,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(7,10)(7,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(7,10)(7,10)(6,6)(6,6)(3,3)
28、(3,3)(0,3)(0,3)(3,3)(3,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(7,10)(7,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(7,10)(7,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(2,2)(2,2)(0,3)(0,3)(0,4)(0,4)增流路：增流路：v0v1v3v4vn增流值增流值=2v0v0v5v5v4v4v3v3v1v1v2v2vnvn(9,10)(9,10)(4,4)(4
29、,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(9,10)(9,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(0,2)(0,2)(0,3)(0,3)(2,4)(2,4)v0v0v5v5v4v4v3v3v1v1v2v2vnvn(9,10)(9,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(9,10)(9,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(0,2)(0,2)(0,3)(0,3)(2,4)(2,4)f =
30、18 判断此时的流是判断此时的流是否是最大流，用定理否是最大流，用定理寻找寻找最小截集最小截集。v0v0v5v5v4v4v3v3v1v1v2v2vnvn(9,10)(9,10)(4,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(9,10)(9,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(0,2)(0,2)(0,3)(0,3)(2,4)(2,4)f =18SS截量截量=5+3+4+6=18两者相等为最大流两者相等为最大流v0v0v5v5v4v4v3v3v1v1v2v2vnvn(9,10)(9,10)(4
31、,4)(4,4)(3,5)(3,5)(5,5)(5,5)(4,5)(4,5)(6,6)(6,6)(9,10)(9,10)(6,6)(6,6)(3,3)(3,3)(0,3)(0,3)(3,3)(3,3)(0,2)(0,2)(0,3)(0,3)(2,4)(2,4)f =18SS截量截量=5+3+4+6=18两者相等为最大流两者相等为最大流或或或或const int inf=0 xfffff;const int N=205;int maxflow,preN,cNN;void Edmonds_Karp(int start,int end,int m)while(1)queue p;int minflo
32、w=inf;p.push(start);/源点为1，进队 memset(pre,0,sizeof(pre);/初始化增广路径数组，题目中的顶点是从1开始的 while(!p.empty()/bfs找增广路 int u=p.front();p.pop();if(u=end)break;for(int i=1;i 0&prei=0)prei=u;p.push(i);/prei除了记录当前顶点的父亲，还记录当前顶点有没被访问过 if(preend=0)break;/顶点的父亲为空，表示找不到增广路，很容易理解吧。for(int i=end;i!=start;i=prei)/找出增广路中最小残余量 m
33、inflow=min(minflow,cpreii);for(int i=end;i!=start;i=prei)cpreii-=minflow;/更新增广路中正反向弧的流量 ciprei+=minflow;maxflow+=minflow;怎样找最小割？增广算法结束时，令已标号节点集合为S，其他节点集合为T（T=V-S）那么（S-T）S到T 的弧就是最小割。Relabel-to-Front算法的时间复杂度是O(V3)，还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V2*E0.5)。我研究了一下HLPP，感觉它和Relabel-to-Front本质上没有区
34、别，因为Relabel-to-Front每次前移的都是高度最高的顶点，所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点，每次对pop出来的顶点discharge，出现了新的溢出顶点时入队。Push-Relabel类的算法有一个名为gap heuristic的优化，就是当存在一个整数0kk的顶点v做更新，若它小于V+1就置为V+1。最大流问题仅注意网络流的流通能力，没有考虑流通的费用。实际上费用因素是很重要的。例如在交通运输问题中，往往要求在完成运输任务的前提下，寻求一个使总运输费用最省的运输方案，这就是最小费用流问题。如果只考虑单位货物的运输费用，那
35、么这个问题就变成最短路径问题，由此可见，最短路问题是最小费用流问题的基础。现已有一系列求最短路的成功方法。最小费用流最小费用流(或最小费用最大流)问题，可以交替使用求解最大流和最短路两种方法，通过迭代得到解决。总结：问题描述：一个工厂要将产品送到火车站，可以有许多道路供其选择，在不同路线上每吨货物的运费并不相同，而且每条路线只能有限重量的货物运输，那么要将w吨的产品从工厂送到火车站，用什么方法可以使运费最少？最小费用问题：最小费用问题：问题描述：算法思路：类似Edmonds-Karp，但每次用Bellman-ford算法求出发点和结束点之间边权（边权可以为负值，在找最短路的时候边权按正值计算但
36、在更新流量的时候要减去相应的流量）的最短路径，然后根据这个路径求增广路流量和费用最小费用问题：最小费用问题：v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,0)(3,3,0)(4,6,0)(4,6,0)(4,3,0)(4,3,0)(3,4,0)(3,4,0)(2,5,0)(2,5,0)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,0)(2,2,0)(1,1,0)(1,1,0)(2,2,0)(2,2,0)(单位运费，边容量，流值）单位运费，边容量，流值）（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,0)(3,3,0)(
37、4,6,0)(4,6,0)(4,3,0)(4,3,0)(3,4,0)(3,4,0)(2,5,0)(2,5,0)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,0)(2,2,0)(1,1,0)(1,1,0)(2,2,0)(2,2,0)将各弧的单位运费作为长度，求将各弧的单位运费作为长度，求v0到到vn的最短的最短增流路增流路v0v1v3v4vn，路长为，路长为8，可增加，可增加1单位的单位的流值。流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,0)(3,3,0)(4,6,0)(4,6,0)(4,3,0)(4,3,0)(3,4,0)(3
38、,4,0)(2,5,0)(2,5,0)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,0)(2,2,0)(1,1,0)(1,1,0)(2,2,0)(2,2,0)将各弧的单位运费作为长度，求将各弧的单位运费作为长度，求v0到到vn的最短的最短增流路增流路v0v1v3v4vn，路长为，路长为8，可增加，可增加1单位的单位的流值。流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,0)(3,3,0)(4,6,0)(4,6,0)(4,3,0)(4,3,0)(3,4,0)(3,4,0)(2,5,0)(2,5,0)(9,3,0)(9,3,0)(2,
39、3,0)(2,3,0)(2,2,0)(2,2,0)(1,1,0)(1,1,0)(2,2,0)(2,2,0)将各弧的单位运费作为长度，求将各弧的单位运费作为长度，求v0到到vn的最短的最短增流路增流路v0v1v3v4vn，路长为，路长为8，可增加，可增加1单位的单位的流值。流值。v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,0)(3,3,0)(4,6,0)(4,6,0)(4,3,0)(4,3,0)(3,4,0)(3,4,0)(2,5,0)(2,5,0)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,0)(2,2,0)(1,1,0)(1,1,0)(2,2,0)
40、(2,2,0)将各弧的单位运费作为长度，求将各弧的单位运费作为长度，求v0到到vn的最短的最短增流路增流路v0v1v3v4vn，路长为，路长为8，可增加，可增加1单位的单位的流值。流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,1)(3,3,1)(4,6,0)(4,6,0)(4,3,0)(4,3,0)(3,4,0)(3,4,0)(2,5,1)(2,5,1)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,0)(2,2,0)将各弧的单位运费作为长度，求将各弧的单位运费作为长度，求v
41、0到到vn的最短的最短增流路增流路v0v1v3v4vn，路长为，路长为8，可增加，可增加1单位的单位的流值。流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,1)(3,3,1)(4,6,0)(4,6,0)(4,3,0)(4,3,0)(3,4,0)(3,4,0)(2,5,1)(2,5,1)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,0)(2,2,0)再求再求v0到到vn的最短增流路的最短增流路v0v1v4vn，路长为，路长为9，可增加可增加2单位的流值。单位的流值。（费用，容量
42、，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,1)(3,3,1)(4,6,0)(4,6,0)(4,3,0)(4,3,0)(3,4,0)(3,4,0)(2,5,1)(2,5,1)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,0)(2,2,0)再求再求v0到到vn的最短增流路的最短增流路v0v1v4vn，路长为，路长为9，可增加可增加2单位的流值。单位的流值。v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,1)(3,3,1)(4,6,0)(4,6,0)(4,3,0)(4,3,0
43、)(3,4,0)(3,4,0)(2,5,1)(2,5,1)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,0)(2,2,0)再求再求v0到到vn的最短增流路的最短增流路v0v1v4vn，路长为，路长为9，可增加可增加2单位的流值。单位的流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,3)(3,3,3)(4,6,0)(4,6,0)(4,3,2)(4,3,2)(3,4,0)(3,4,0)(2,5,3)(2,5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1
44、)(2,2,1)(1,1,1)(1,1,1)(2,2,0)(2,2,0)再求再求v0到到vn的最短增流路的最短增流路v0v1v4vn，路长为，路长为9，可增加可增加2单位的流值。单位的流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,3)(3,3,3)(4,6,0)(4,6,0)(4,3,2)(4,3,2)(3,4,0)(3,4,0)(2,5,3)(2,5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,0)(2,2,0)再求再求v0到到vn的最短增流路的最短增流路v0v2v
45、5vn，路长为，路长为9，可增加可增加2单位的流值。单位的流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,3)(3,3,3)(4,6,0)(4,6,0)(4,3,2)(4,3,2)(3,4,0)(3,4,0)(2,5,3)(2,5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,0)(2,2,0)再求再求v0到到vn的最短增流路的最短增流路v0v2v5vn，路长为，路长为9，可增加可增加2单位的流值。单位的流值。v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,
46、3,3)(3,3,3)(4,6,0)(4,6,0)(4,3,2)(4,3,2)(3,4,0)(3,4,0)(2,5,3)(2,5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,0)(2,2,0)再求再求v0到到vn的最短增流路的最短增流路v0v2v5vn，路长为，路长为9，可增加可增加2单位的流值。单位的流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,3)(3,3,3)(4,6,2)(4,6,2)(4,3,2)(4,3,2)(3,4,2)(3,4,2)(2,5,3)(2,
47、5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,2)(2,2,2)再求再求v0到到vn的最短增流路的最短增流路v0v2v5vn，路长为，路长为9，可增加可增加2单位的流值。单位的流值。（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,3)(3,3,3)(4,6,2)(4,6,2)(4,3,2)(4,3,2)(3,4,2)(3,4,2)(2,5,3)(2,5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,
48、2,2)(2,2,2)再求再求v0到到vn的最短增流路的最短增流路v0v2v3v1v4vn，路长为，路长为14，可增加，可增加1单位的流值。（单位的流值。（v3v1反向弧，同反向弧，同最大流处理）最大流处理）（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,3)(3,3,3)(4,6,2)(4,6,2)(4,3,2)(4,3,2)(3,4,2)(3,4,2)(2,5,3)(2,5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,2)(2,2,2)再求再求v0到到vn的最短增流路的最
49、短增流路v0v2v3v1v4vn，路长为，路长为14，可增加，可增加1单位的流值。（单位的流值。（v3v1反向弧，同反向弧，同最大流处理）最大流处理）（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,3)(3,3,3)(4,6,2)(4,6,2)(4,3,2)(4,3,2)(3,4,2)(3,4,2)(2,5,3)(2,5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,2)(2,2,2)再求再求v0到到vn的最短增流路的最短增流路v0v2v3v1v4vn，路长为，路长为14，可增
50、加，可增加1单位的流值。（单位的流值。（v3v1反向弧，同反向弧，同最大流处理）最大流处理）（费用，容量，流量）v0v0v3v3v5v5v2v2v1v1v4v4vnvn(3,3,3)(3,3,3)(4,6,2)(4,6,2)(4,3,2)(4,3,2)(3,4,2)(3,4,2)(2,5,3)(2,5,3)(9,3,0)(9,3,0)(2,3,0)(2,3,0)(2,2,1)(2,2,1)(1,1,1)(1,1,1)(2,2,2)(2,2,2)再求再求v0到到vn的最短增流路的最短增流路v0v2v3v1v4vn，路长为，路长为14，可增加，可增加1单位的流值。（单位的流值。（v3v1反向弧，同