D - 浮気予防 (abc010_4) 最大フロー・最小カット

Quiz

https://atcoder.jp/contests/abc010/tasks/abc010_4

Submit

https://atcoder.jp/contests/abc010/submissions/4065384

  • 意外とTLEにもならず一発で通って良かった
  • パスを何度も求めるのを関数化したのが良かった
    • 見やすい
    • 変数名の自由度が上がる

学び

  • 最小カットとして捉えられるように終端ノードを足す
  • 最大フロー = 最小カット
  • 最大フローの求め方

流してCapacityを更新

f:id:peroon:20190122004307j:plain

逆流するとは、流れをつなぎかえるということ

f:id:peroon:20190122005520j:plain

参考

http://www.hongo.wide.ad.jp/~jo2lxq/dm/lecture/09.pdf