読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

yukicoder No.177 制作進行の宮森あおいです!

最大フロー yukicoder

8月後半〜9月末まではインターンとかで忙しくて中々書けなかったが、そろそろCodeFestival2016本戦に向けて再開していきたい。

解法

オーソドックスな最大フローの問題
source → 原画マン作画監督 → sink という感じで枝を貼ってフローを流して、最大フローがW以上ならOKとなる。
具体的には、

計算量

実装がDinicだと|V|=O(N+M), |E|=O(NM)なので、
全体ではO(|E||V|^2)=O(NM(N+M)^2)で、2.5*10^7 くらい

コード

実際は44msくらいで通る。