n-knuu's logs

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

AtCoder Beginner Contest 004 D. マーブル

最小費用流の問題が欲しくて探していたら、以前別解で解いた問題があったので、解き直した

解法

最小費用流問題で定式化できる。
頂点: source, sink, 赤, 緑, 青, -500~500の箱
辺の貼り方:
source→赤, 緑, 青 にそれぞれR, G, Bの容量、コスト0の辺を張る
赤, 緑, 青→ -500~500の箱 に容量1、それぞれの初期位置の箱と各箱との距離のコストの辺を張る

  • 500~500の箱→sink に容量1、コスト0の辺を張る

コード


感想

最小費用流難しい