AtCoder Beginner Contest 004 D. マーブル
最小費用流の問題が欲しくて探していたら、以前別解で解いた問題があったので、解き直した
解法
最小費用流問題で定式化できる。
頂点: source, sink, 赤, 緑, 青, -500~500の箱
辺の貼り方:
source→赤, 緑, 青 にそれぞれR, G, Bの容量、コスト0の辺を張る
赤, 緑, 青→ -500~500の箱 に容量1、それぞれの初期位置の箱と各箱との距離のコストの辺を張る
- 500~500の箱→sink に容量1、コスト0の辺を張る
コード
感想
最小費用流難しい