简单最大流算法-EK (2)最大容量算法

  最大容量路径算法 (Maximum Capacity Path Algorithm)

 1972年还是那个 E-K 组合提出的另一种最大流算法。每次寻找增广路径时不找最短路径，而找容量最大的。可以预见，此方法与 SAP 类算法相比可更快逼近最大流，从而降低增广操作的次数。实际算法也很简单，只用把前面 E-K 算法的 BFS 部分替换为一个类 Dijkstra 算法即可。USACO 4.2 节的说明详细介绍了此算法，这里就不详述了。

 时间复杂度方面。BFS 是 O(E)，简单 Dijkstra 是 O(V²)，因此效果可想而知。但提到 Dijkstra 就不能不提那个 Heap 优化，虽然 USACO 的算法例子中没有用 Heap ，我自己还是实现了一个加 Heap 的版本，毕竟 STL 的优先队列太好用了不加白不加啊。效果也是非常明显的，但比起 Dinic 或 ISAP 仍然存在海量差距，这里就不再详细介绍了。

这是算法的伪代码

1   IF (源点 = 汇点)
2       总流 = 无限大
3       DONE
 
4   总流 = 0
 
5   WHILE (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            退出循环
24        visited(MaxLoc) =   TRUE
25        #   调整相邻节点
26        FOR MaxLoc的所有相邻节点   i
27          IF (flow(i)(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

最大增广路径为(5,1,3,6,2)

瓶颈弧是1->3，容量为5。因此，把路径上所有的弧减去5，把反向弧上加上5（如果需要，添加弧）。这就是得到的图：

在新的图里，最大增广路径为(5,4,6,2)

瓶颈容量为3，再来一次。

现在网络的最大容量路径为(5,4,6,3,2)

瓶颈为1，再来一次

结果图从源到汇就没有增广路径了。唯一可以到达的源点的就是它自己和1号节点

算法加了三次流，第一次是5，第二次是3，最后一次是1。因此，最大流是9。