sab*_*ari 8 graph network-flow max-flow
给定有向加权图,如何在所有顶点对之间找到最大流量(或最小边缘切割).
天真的方法就是调用像Dinic这样的Max Flow算法,其复杂度O((V^2)*E)为每对.
因此对于所有对都是如此O((V^4)*E).
是否有可能降低复杂性,O((V^3)*E)或O(V^3)通过一些优化？
Gomory-Hu Tree不适用于有向图，抛开这一点，Gomory-Hu Tree 将通过应用最小割形成图最大流。
时间复杂度为：
O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2)
* 使用最优最小割算法（Max-Flow Min-Cut Reduction）
这个例子说明了如何从给定的图构建 Gomory-Hu 树