ei1333's page

ホーム > Wiki

最大流(Dinic)

説明

最大流を求める。最短の増加パスを探して、そこにフローを流していくことを繰り返す。そのような経路がなくなったら残余パスでもう一度それを繰り返す。それでも、流せなくなったら終了する。実際の計算量よりも高速に動作することが知られている。

計算量

$O(E V^2)$

実装例

問題例