Her*_*ler 6 algorithm flow graph
给定无向图,所有边都有权重1; N,M约为10 ^ 6我需要找出源和汇之间的流量是否大于某个值X.X非常小.
使用bfs直到流量等于X得到O(M*X),这对我来说太慢了.
有没有更快的方法来估算流量？
ilo*_*ahz 1
你需要的基本上是 maxflow，请参阅http://en.wikipedia.org/wiki/Maximum_flow_problem
实用高效，推荐使用Dinic算法。
如果您需要一些示例，您可以参考我的代码之一，位于http://wiki.attiix.com/index.php?title=Maxflow
归档时间：
13 年，4 月 前
查看次数：
235 次
最近记录：