[graph/flow] Dinic's algorithm

[ei1333]

Description

最大流

Time complexity

ref. https://misawa.github.io/others/flow/dinic_time_complexity.html

• $O(n^2 m)$
• 辺の容量が整数の時
  • 流量を $F$ として $O(Fm)$
  • 辺の容量の最大値を $k$ として $O(km^{\frac 2 3})$ など

File Name

src/graph/dinic.hpp

TODO

• [x] 実装
• [ ] ドキュメント作成
• [ ] unit-test
• [x] verify

note

• その他の最大流を求めるアルゴリズム
  • Dinic （動的木笑）: $O(nm \log n)$
  • Ford Fulkerson: $O(Fm)$　-> Dinic の下位互換なので使う場面はないとおもっている
  • Goldberg-Tarjan: $O(n^3)$ -> 密なグラフの場合
• 最小流量制約がある場合
• implementation
  • (url)
• 関連 issue / PR

  • 45

• verify:
  • Maximum Flow

[Luzhiled]

いや、なんで graph/flow/ 以下に作られていないんだよ