给定一个有向加权图，如何找到最大流量 ( or 最小切边）在所有顶点对之间。
天真的方法就是简单地调用Max Flow像 Dinic 的算法，其复杂度为O((V^2)*E)，对于每对。
因此对于所有对来说都是O((V^4)*E).
是否可以将复杂度降低到O((V^3)*E) or to O(V^3)通过一些优化？
戈莫里-胡树不适用于有向图，抛开这一点，Gomory-Hu Tree将通过应用最小割形成一个Graph最大流。
时间复杂度为：
O(|V|-1 * T(minimum-cut)) = O(|V|-1 * O(2|V|-2)) ~ O(|V|^2)
* 使用最优的最小割算法 （最大流量最小切割减少)
This example说明如何从给定的图构建 Gomory-Hu 树
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
