Dinicの速さ
Dinicの計算量はO(V^2E)で、EがVに比例する時V=10000では解けなさそうに思うわけだが「現実にはもっと速い」とされて、実際速い、じゃあどれくらい速いのか 辺の容量が整数である時にいくつかの条件で計算量が減る
最大流がFの時 $ O(FE)
辺の容量が高々Cの時$ O(C E^{3/2})
かつ多重辺がない時 $ O(CV^{2/3}E)
各頂点を流れるフローが高々Fのとき $ O(FV^{1/2}E)
二部マッチングを最大フローで解く場合は上記のF=1の場合に相当する
動的木を使う実装の場合、一般のグラフに対して $ O(VE\log V)
辺容量が定数の場合$ O(\min \{ E^{1/2}, V^{2/3} \} E) PDF