网络流现在想将一些物资从

1、网络流运输网络现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。 每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？4248473 621STV1V2V3V4公路运输图流网络流网络(flow netword): G=(V,E)是一个有向图，其中每条边 E 均有一非负容量c(u,v) 0。简称网络。如果不存在边，则令c(u,v)=0；如果c(u,v)=0，可认为边不存在；两个特殊点：源点和汇点源点s：入度为零，即d-(s) = 0汇点t： 出度为零，即d+(t) = 0网络流(flow)网络流是一个实值函数f : V X V

2、 R，且满足三个性质：容量限制: f(u,v) = c(u,v)反对称性：f(u,v) = - f(v,u)流量平衡: 对于不是源点也不是汇点的任意结点,流入该结点的流量和等于流出该结点的流量和。uf(u,v) = wf(v,w) 有歧义的写法：vf(u,v) = 0 uV- s,t 最大流流 f 的值定义为 | f | = 网络中的最大流(maximum flow) 是指流值最大的流。解最大流问题的三个概念残量网络增广路割残量网络给定流网络G=(V,E)，设f为G中的一个流。对于G中的每条边 E，可以定义残留容量r(u,v) = c(u,v) f(u,v)。通俗地讲：残留容量就是对于某一条边

3、（弧），能再有多少流量通过。残量网络为Gf = (V, Ef)，其中边集 Ef = | r(u,v) 0 残留网络中的边既可以是E中边，也可以是它们的反向边。例1v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)v1tsv2232422原网络 (a,b)表示(流量f,容量c)残量网络（如果网络中一条边的容量为0,则认为这条边不在残量网络中。r(s,v1)=0,所以就不画出来了。另外举个例子：r(v1,s) = c(v1,s) f(v1,s) = 0 (-f(s,v1) = f(s,v1) = 4.图1图2例1 从残量网络中可以清楚地看到：边(s,v2) = 3,从S到v2还可以再增

4、加3单位的流量；存在边(v1,t) = 2,从v1到t还可以再增加2单位的流量。v1tsv2232422后向弧其中像(v1,s)这样的边称为后向弧,它表示从v1到s还可以增加4单位的流量。但是从v1到s不是和原网络中的弧的方向相反吗？显然“从v1到s还可以增加4单位流量”这条信息毫无意义。那么，有必要建立这些后向弧吗？v1tsv2232422为什么要建立后向弧显然，例1中的画出来的不是一个最大流。但是，如果我们把s - v2 - v1 - t这条路径经过的弧的流量都增加2,就得到了该网络的最大流。注意到这条路径经过了一条后向弧:(v2,v1)。如果不设立后向弧，算法就不能发现这条路径。从本质上

5、说，后向弧为算法纠正自己所犯的错误提供了可能性，它允许算法取消先前的错误的行为（让2单位的流从v1流到v2)增广路（可改进路）增广路：残量网络上的一条从s到t的简单路径，其中任意一条弧(u,v)，都有ru,v0。绿色的即为一条增广路。v1tsv2232422弧的分类给定的流网络G=(V,E)中，设f为G中的一个流饱和弧：网络中f(u,v) = c(u,v)的弧；非饱和弧：网络中f(u,v) 0 的弧；前向弧：原图中的弧；后向弧：原图中弧的反向弧；增广流量增广路的每一条前向弧都是非饱和弧，每一条后向弧都是非零流弧；增广路的残留容量为沿该路径增加的最多的流量，r(p) = min r(u,v) |

6、 P YY最大流: 从0流开始，不断寻找增广路。割（cut）网络的割S,T将点集V分成两个集合S和TS+T = V ，S T = s S.t T.符号S,T表示边集合| u S,v T, E如果f是一个流，S,T的净流为f(S,T) =f(x,y) (xS,yT)，S,T的容量为c(S,T)= c(x,y) (xS,yT) .S,T=, 正向T,S=, 负向右图练习：计算c(S,T)时，只算S,T；计算f (S,T)时，T,S的流值要计算在内，负值割的例子v1tsv2(2,2)(4,4)(2,4)(0,3)(2,2)一些结论结论1：任意割的流量小于等于割的容量结论2：任意割的流量等于整个网络的

7、流量.结论3：任意一可行流为f，任意一割为 U, W ，必有：| f | c(U, W)。最大流最小割定理网络流中这三个条件等价:1、f是最大流2、残量网络中找不到增广路径3、|f| = c(S,T)证明1 - 2: 显然.假设有增广路径,由于增广路径的容量至少为1,所以用这个增广路径增广过后的流的流量肯定要比f的大,这与f是最大流矛盾.2 - 3：构造割S,T，S为残量网络s能到达的点；T为残量网络能到达t的点。割S,T中，原图的前向弧都为饱和弧，原图的后向弧都为0弧。因此 | f | = c(S,T).3 - 1: 由前面的结论3 和 | f | = c(S,T)， f 是最大流，S,T是

8、最小割。增广路算法（Augmenting Path ）网络流算法主要有两类：增广路和预流推进。Ford-Fulkerson 方法 (G,s,t)1 将各边上流量 f 初始化为0;2 while 存在一条增广路径 p do 沿路径 p 增广流量 f;3 return f所有增广路算法的基础都是 Ford-Fulkerson 方法，称之为方法而不是算法是因为只提供了一类思想 。增广路算法的正确性如果最大流最小割定理不能从2推出3,那么存在这样一种可能性: 尽管找不到增广路径了,但由于前面的错误决策,导致f还没有到达最大流,却不能通过修改当前流来得到最大流.但由于最大流最小割定理的三个条件互相等价(

9、1-2,2-3,3-1), 一个流是最大流当且仅当它没有增广路径.增广路算法的效率设n = |V|, m = |E|每次增广都是一次BFS,效率为O(m)所以,总共的时间复杂度为O(m*f*)其中f*为增广次数.怎么求f*?f*的理论上界考虑每一次增广,至少有一条边的r(u,v)值等于增广路径的流量.称这些边为临界边.增广之后,这条临界边就在残量网络中消失.假设一条临界边对应一次增广(事实上很难达到这样),令每条边成为临界边的次数为k(u,v),则有f* = O(m*k).k的上界?k的上界如果要让一条曾经的临界边(u,v)再次成为临界边,则必须有一条增广路径包含边(v,u).因为每次增广之后

10、临界边就消失,要让他再次成为临界边至少要让他再次在残量网络中出现,即(v,u)要被增广.可以证明,当算法取的增广路总是残量网络中的最短路,任意一条边成为临界边的次数至多为n/2-1.因此,增广路算法的效率为O(f*m) = O(km2) = O(nm2). (这只是个上界,一般情况是达不到的)SAP沿路径 p 增广流量 f 的操作基本都是相同的，各算法的区别就在于寻找增广路径 p 的方法。例如寻找从 s 到 t 的最短路径( Shortest Augmenting Path,SAP) ，或流量最大的路径。SAP算法Edmonds - Karp 算法 Dinic 算法 Improved SAP

11、算法 Edmonds - Karp 算法Shortest Augmenting Path1 x t3 do 找一条最短的增广路径 P4 delta - minrij:(i,j) 属于 P5 沿 P 增广 delta 大小的流量6 更新残量网络 Gx7 return xE-K 算法 : 每次使用BFS寻找最短增广路；O(nm2)分层网络BFS 寻找终点太慢，DFS 不能保证找到最短路径。1970年 Dinic 提出用分层网络较快找到最短增广路分层网络 AN(f)：在残量网络中从源点 s 起始进行 BFS，这样每个顶点在 BFS 树中会得到一个距源点 s 的距离 d。 d(s) = 0，直接从 s

12、 出发可到达的点距离为 1，下一层距离为2 . 。称所有具有相同距离的顶点位于同一层。在分层网络中，只保留满足条件 d(i) + 1 = d(j) 的边（允许弧），这样在分层网络中的任意路径就成为到达此顶点的最短路径。Dinic 算法 1 用一遍 BFS 构建分层网络 AN(f)2 while t 在AN(f) 中3 AN(f) 中用一遍 DFS 找到所有到终点 t 的路径增广用一遍 BFS 构建分层网络 AN(f)实际代码中不必真的用一个图来存储分层网络，只需保存每个顶点的距离标号；在 DFS 时判断 disti + 1 = distj 即可。Dinic 的时间复杂度为 O(n2m)。Din

13、ic 算法1while true do2 用一遍 BFS 构建分层网络 AN(f)3 if t 不在 AN(f) then 结束4 AN(f) 中用一遍 DFS 找到所有到终点 t 的路径增广5 end while实际代码中不必真的用一个图来存储分层网络，只需保存每个顶点的距离标号；在 DFS 时判断 disti + 1 = distj 即可。Dinic 的时间复杂度为 O(n2m)。ISAP算法ISAP充分利用了距离标号的作用，每次发现顶点无出弧时不是像 Dinic 算法那样到最后进行 BFS，而是就地对顶点距离重标号，这样相当于在遍历的同时顺便构建了新的分层网络，每轮寻找之间不必再插入全图

14、的 BFS 操作，提高了运行效率。 与 Dinic 算法不同，ISAP 中的距离标号是每个顶点到达终点 t 的距离。同样也不需显式构造分层网络，只要保存每个顶点的距离标号即可。algorithm Improved-Shortest-Augmenting-Path1 f - 02 从终点 t 开始进行一遍反向 BFS 求得所有顶点的起始距离标号 d(i)3 i - s4 while d(s) ndo5 if i = t then / 找到增广路6 Augment7 i - s / 从源点 s 开始下次寻找8if Gf 包含从 i 出发的一条允许弧 (i,j)9then Advance(i)10e

15、lse Retreat(i) / 没有从 i 出发的允许弧则回退11 return f procedure Advance(i)1 设 (i,j) 为从 i 出发的一条允许弧2 pi(j) - i / 保存一条反向路径，为回退时准备3 i - j / 前进一步，使 j 成为当前结点procedure Retreat(i)1 d(i) - 1 + mind(j):(i,j)属于残量网络Gf/ 重标号操作2 if i != s3 then i - pi(i) / 回退一步procedure Augment1 pi 中记录为当前找到的增广路 P2 delta - minrij:(i,j)属于P3 沿

16、路径 P 增广 delta 的流量4 更新残量网络 Gf 算法分析ISAP 算法时间复杂度与 Dinic 相同都是 O(n2m)ISAP 的GAP 优化。由于从 s 到 t 的一条最短路径的顶点距离标号单调递减，且相邻顶点标号差严格等于1，因此可以预见如果在当前网络中距离标号为 k (0 = k n) 的顶点数为 0，那么可以知道一定不存在一条从 s 到 t 的增广路径，此时可直接跳出主循环。 GAP优化对ISAP至关重要；算法实现数据结构：直接存储残量网络，每条边都有前向边和后向边，前向边初始化为容量，后向边初始化为0. 求流量，可保存容量，减残量。也可直接保存流量。距离标号h ，间隔优化 gap ;反向边：每个边结点都保存rev指针。使用静态链表时，可以让相邻保存，p和p1互为反向边，要求从下标0开始使用。其它说明反向BFS:由于ISAP能自动重建分层网络，不一定写反向bfs.当前弧优化：如果说在某次迭代中从i出 发的弧(i,j)不是允许弧，则在顶点i的标号修改之前(i,j)都不可能是允许弧。（因为d(i)不变，d(j)不减且d(i)d(