Network Flow
网络流
译 By Thunder
问题预备
最短路
问题
给出：一个有向连通带权图，包含源点和汇点。
每一条弧的权表示那条弧的容量。一个图的流通过分配整数量给每条边来达到：
·通过每条弧的流不大于这条弧的容量
·除了源点和汇点的每个点，流入量等于流出量
取源点的流出总量减去流入总量（或汇点的流入总量减去流出总量的最大值
例
给出：水管的设计和每条水管的容量。水管里的水必须从上往下流，所以每条水管里，水只能向一个方向流。
计算能从头（自来水厂）流到尾（您的农场）的水量。
算法：
算法（贪心）通过迭代增加从源到汇的流来建立网络流。
从每条弧的权等于初始的权开始（弧的权符合那条弧里还未使用的容量）。//-_-#
给出当前的图，找到从源到汇的一条路径，这条路径上的弧都是非0权。计算这条路径的最大流，叫它路径容量。//传说中的增广路径... 路径容量 = 瓶颈容量
对于每一条路径上的弧，给弧的权减去路径容量。另外，给路径中的反向弧（在相同两点之间的弧，不过方向相反）加上等于和路径容量相等的权（只要反向弧存在，就增加它的权）//调整增广路径
继续调整路径直到没有增广路径存在。
这能保证停止，因为您加上每次至少一单位流（权总是整数），并且流严格单调递增。增加反向弧的权相当于减少路径上的流量。
如果您对算法的细节分析感兴趣，请教Sedgewick.//谁啊..-_-....
这是算法的伪代码：
1 IF (源点 = 汇点)
2 总流 = 无限大
3 DONE
4 总流 = 0
5 WHIEL (TRUE)
6 # 找到从源到汇的最大的容量的路径
7 # 用修改过的Dijkstra算法 //在Chapter 4 的ditches就要用Bellman-Ford了..
8 FOR 所有的顶点 i
9 prevnode(i) = nil
10 flow(i) = 0
11 visited(i) = FALSE
12 flow(源点) = 无限大
13 WHILE (TRUE)
14 最大流 = 0
15 最大流节点 = nil
16 # 找到最大容量的未访问节点
17 FOR 每个顶点i
18 IF (flow(i) > MaxFlow AND NOT visited(i))
19 MaxFlow = flow(i)
20 MaxLoc = i
21 IF (MaxLoc = Nil)
22 退出循环
23 IF (MaxLoc = 汇点)
24 退出循环
24a visited(MaxLoc) = TRUE
25 # 调整相邻节点
26 FOR MaxLoc的所有相邻节点 i
27 IF (flow(i) < min(MaxFlow, MaxLoc到i的容量))
28 prevnode(i) = MaxLoc
29 flow(i) = min(MaxFlow, MaxLoc到i的容量))
30 IF (MaxLoc = Nil) # 没有路径
31 退出循环
32 路径容量 = flow(汇点)
33 总流 = 总流 + 路径容量
# 把那个流加到网络里 适当调整容量
35 当前节点 = 汇点
# 对于增广路径上每条弧, prevnode(当前节点), 当前节点
36 WHILE (当前节点不为源点)
38 下一个节点 = Prevnode(当前节点)
39 下一个节点到当前节点的容量减去路径容量
40 当前节点到下一个节点的容量加上路径容量
41 当前节点 = 下个节点
这个方法的运行时间为O(FM)，F是最大流 M是弧的数目. 运行时间通常更短, 因为算法每次总是尽可能大的提升流。
为了确定每条弧上的流，比较开始的容量和最后的容量。如果最后的容量变少了，区别就在于通过这条弧的流。
当有回路的时候，这个算法可能产生死循环。
实例
考虑下面那个网络，源点为5，汇点为2
Graph1
最大增广路径为(5,1,3,6,2)
Graph2
瓶颈弧是1->3，容量为5。因此，把路径上所有的弧减去5，把反向弧上加上5（如果需要，添加弧）。这就是得到的图：
Graph3
在新的图里，最大增广路径为(5,4,6,2)
Graph4
瓶颈容量为3，再来一次。
Graph5
现在网络的最大容量路径为(5,4,6,3,2)
Graph6
瓶颈为1，再来一次
Graph7
结果图从源到汇就没有增广路径了。唯一可以到达的源点的就是它自己和1号节点
Graph8
算法加了三次流，第一次是5，第二次是3，最后一次是1。因此，最大流是9。
扩展
网络流问题是很广泛的，通常和图结合在一起。
扩展到无向图，只需要简单的把无限边扩展为两条相反方向的弧就可以了。
如果您想要限制任意一个节点的通过量，把一个节点拆成两个，一个流入节点，一个流出节点，把流入的弧连到流入节点里，流出弧连到流出节点里，在流入节点和流出节点之间加上一条弧，容量为限制。
如果您有多源点汇点，建立一个虚拟的源点和虚拟的汇点，虚拟的源点射出弧到每个源点，汇点射出弧到虚拟汇点。容量无限。
如果您有实数型的权，这个问题不再保证能出解，尽管答案能逐渐逼近。
可选问题
网络流能用来解决其他的一些不明显的问题。
最大匹配
给出两个对象集合（叫他们A和B），你想要把A和B中的元素尽可能多的匹配起来，约束条件是只可以两两配对。这就是最大匹配问题。
把这个问题用网络流的形式表现出来，建立一个源点，射出容量为1的弧给A的元素，建立一个汇点，B中的元素射出容量为1的弧。另外，如果A中某个元素可以和B中某个元素匹配，从A的这个元素向B的那个元素射出一条容量为1的弧。用网络流算法确定哪些A元素到B元素的弧被用到。
最小割
给出一个带权无向图，最小割就是一个权和最小的，能够把两个给出点分开的边的集合。
最小的权和就是两个节点之间的流。
要确定路径，按照权递增的顺序尝试删除每条边，看它是否减少了网络流，减少量为边的容量。第一个这样的边就是最小割的元素，去掉这条边继续在图上操作。
用相同的技巧，把节点用容量限制，这能够扩展到求节点的割。有向图也是一样。然而，它不能够解决所谓的“最佳匹配”问题，每一对都有一个“佳值”，而且您想要得到最高“佳值”和的匹配。
例题
如果问题讨论取流或者其他从一个地方到另一个地方东西的移动的最优值，就可以几乎确定是最大流。如果它讨论的任何一类东西的最大配对，就可能是最大匹配。
病毒流
您有一个通过网线连接的计算机网络。数据可能从任何一个方向流经网线。不幸的是，一台网络里的机器染上病毒，您需要从中心服务器隔离这台机器来防止病毒传染。给出关闭一对机器连接的代价，计算控制病毒传染到服务器的最小的代价。
这就是最小割问题。
伐木工人的计划
不同种类的树需要雇佣拥有不同的技巧的伐木工人来正确的砍树。不管哪种树或伐木工人，砍一棵树需要30分钟。给出伐木工人的信息，和哪种树需要哪位才能正确的砍倒，以及数的信息，计算在半小时内砍倒的最多的树的数目。
牛的电话联系（USACO 锦标赛 1996）
给出原野里的一组电脑，和电脑之间连着的网线，要想阻止给定两台电脑的联系 最少需要关掉多少网络中的电脑。假定两台给出的电脑没有关掉。
这相当于最少节点割的问题。两台给出的电脑标上源点和汇点。电缆是双向的。把每个点拆成流入点和流出点，这样我们就能够用1限制任何一台电脑。现在，网络里的最大流就相当于节点最小割了。
为了具体确定割，反复删除节点，直到您找到一个能降低网络流量的节点。
科学展览审定
一个科学展览由N个学科，和M个裁判。每个裁判愿意审定某些学科，每个学科需要一些裁判。每个裁判只能够审定在给出的科学展览中的一个学科。您在这些条件下总共能分配给多少裁判任务？
这是一个很类似最大匹配的问题，除了每个学科需要可能多于一个裁判。解决这个问题的最简单的方法是把从科目到汇点的弧的容量赋予需要裁判数的值。
石油管道设计
给出阿拉斯加管道线的设计（每条管道的容量，和管道如何连接），以及每个交点的位置，您想提高朱诺和费尔班柯斯之间最大流量，但您的钱只够添加一条容量为X的管道。此外，管道只能10英里长。这条管道添加在哪两个交点能最大程度的提高流量？
要解决这个问题，对于距离10英里以内的每一对交点，添加一条管道，再计算从朱诺到费尔班柯斯的流量增加值。每一个子问题都是最大流。
: 科技
