algorithm - グラフで流れを推定する

Question

無向グラフの場合、すべての辺の重みは 1 です。N、M は約 10^6 です。ソースとシンクの間のフローがある値 X よりも大きいかどうかを調べる必要があります。X は非常に小さいです。

フローが X に等しくなるまで bfs を使用すると、O(M*X) が得られますが、これは私には遅すぎます。

フローを推定するより迅速な方法はありますか?

Answer 1

必要なのは基本的に maxflow です。http://en.wikipedia.org/wiki/Maximum_flow_problemを参照してください。

実用的な効率のためには、Dinic のアルゴリズムが推奨されます。

例が必要な場合は、http://wiki.attiix.com/index.php?title=Maxflow にある私のコードの 1 つを参照してください。