给定无向图，所有边的权重为 1；N, M 约为 10^6 我需要找出源和汇之间的流量是否大于某个值 X。X 非常小。
使用 bfs 直到流量等于 X 给出 O(M*X) 这对我来说太慢了。
有没有更快的方法来估算流量？
问问题
281 次
1 回答
1
你需要的基本上是maxflow，见http://en.wikipedia.org/wiki/Maximum_flow_problem
并且建议使用Dinic 算法以提高实用效率。
如果您需要一些示例，您可以参考我的代码之一，位于http://wiki.attiix.com/index.php?title=Maxflow
于 2012-09-04T16:40:06.217 回答