2016-10-15 yukicoder No.177 制作進行の宮森あおいです！ 最大フロー yukicoder 8月後半〜9月末まではインターンとかで忙しくて中々書けなかったが、そろそろCodeFestival2016本戦に向けて再開していきたい。 問題 No.177 制作進行の宮森あおいです！ - yukicoder 解法 オーソドックスな最大フローの問題 source → 原画マン → 作画監督 → sink という感じで枝を貼ってフローを流して、最大フローがW以上ならOKとなる。 具体的には、 sourceから原画マンiには、容量J_iの枝を張る 作画監督iからsinkには、容量C_iの枝を張る 原画マンiから作画監督jには、二人の絵が合う場合に容量INFの枝を張る 計算量 実装がDinicだと|V|=O(N+M), |E|=O(NM)なので、 全体ではO(|E||V|^2)=O(NM(N+M)^2)で、2.5*10^7 くらい コード 実際は44msくらいで通る。
