构造辅助网络后如何用最大流算法求最小割

Question

如题所述

Answer 1

在算法中一般存在最大-最小定理。

1 、最大匹配<==>最小覆盖

2、 最大流<==>最小割

最大流-最小割定理理解引自呆欧的形象表达：“多粗的管子，水就最多多大流量”，比如从自来水厂到用水大户工业小区A 能达到的水的最大流量是多大？考虑到可能从水厂到小区有不少到达的水管，那么最大的流量等于拆掉最少最细的水管后水厂不能给小区A 供水的那些水管流量的集合。当然这种说法并不不严谨，因为这里水管不是双向的，而在网络中谈论的信息流却可是是双向的。

其实最大流-最小割最难的地方在于构图了，还有必须掌握Dinic算法。

高效的求最大流算法——Dinci算法：

Dinci算法是基于“层次图”的时间效率优先的最大流算法。

层次：从源点走到终点的最短路长度。层次图：每次从源点到终点距离最短并且记录了多条增广路径（在找到最短路的过程记录了多条增广路径，因为找最短路径的过程中自然有分叉，有分叉那么增广路径条数不就变多了么）。在dfs遍历的时候必须按照层次走。

Dinic算法的思想是为了减少增广次数，建立一个辅助网络L，L与原网络G具有相同的节点数，但边上的容量有所不同，在L上进行增广，将增广后的流值回写到原网络上，再建立当前网络的辅助网络，如此反复，达到最大流

Dinic三步曲：

1、利用原网络构造层次图，顺便判断原网络还有无增广路。

2、利用构造的层次图求此次的最大流，若找不到增广路了则算法结束

3、更新原网络，即增广过程中遇见的边其正边以及逆边的的容量大小。

重复上述的三步。