最小費用流の予習 min cost flow

アルゴリズム

http://www.prefield.com/algorithm/graph/primal_dual.html

• ポテンシャルについては下記

最小費用流

http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout13.pdf

• 図がステップ毎に丁寧に書かれているので理解できた
• 書けそうと思える

実践

• マーブル
  • https://abc004.contest.atcoder.jp/tasks/abc004_4
  • AC. https://atcoder.jp/contests/abc004/submissions/4272722
• E - MinCostFlow
  • https://atcoder.jp/contests/practice2/tasks/practice2_e
  • 解説 https://twitter.com/TeruMiyake/status/1305504444956594177/photo/1
  • 行と列の双方の条件を立てながらいい感じに選ぶ→最小費用流かも。流量とコストを適切に決めるのがポイント🤔

min cost flowを使って解ける問題

• (1800)Chef Monocarp
  • https://codeforces.com/contest/1437/problem/C

注意点

• ✅AC 輪投げ https://atcoder.jp/contests/past202005-open/submissions/22455319
• ACL mincostflowにてcostは0以上である必要がある
• 最大得点→最小コストに読み替えて辺を貼るときにcostが負になるならゲタを履かせる必要がある（2行上の提出を参照）