最小カットに帰着
問題リスト
最適な選択を見つける問題
典型的なパターン
100×100のグリッドを二色で塗り分ける
2択の選択肢が100個くらいある
その選択によってコストや報酬が発生する
選択の間に依存関係がある
選択を頂点の二色の塗りで表現する
この塗りの色をSとTと呼ぶ
2つの頂点スタートとゴールを導入する
これはそれぞれSとTで塗られている
この頂点自体をSとTと表現することもある、ぼくはコード上はstartとgoalで、図に書く時にSとT
二択の選択肢なら自然に対応する
最小カットに帰着する上では「辺の両端の色が違えばコスト発生」「コストを最小化したい」が基本形
頂点Sから頂点vに重みxの辺を引いたら「vがTならコストx支払う」の意味
頂点vから頂点Tに重みxの辺を引いたら「vがSならコストx支払う」の意味
スコアを最大化する問題なら「スコアの減少」をコストにする
すべてのスコアを得られる場合をオフセットとし、そこからの減少分をコストとみなす
このフェーズでは辺の値が負であることを気にしない、後で対処するから。
制約「頂点uがSなら頂点vもS」を辺uvの重みを十分大きくすることで表現する
双方向にすればu=vの表現になる
グラフが構築できたら最大流に対応づけて解く
しかしコストが負の辺があるとうまく対応づけられない
負の容量の辺になって意味不明になる
なので負の辺を除去する作業をここでやる
負の辺-xがつながっている頂点vに注目
頂点vの色はSかTかのどちらか
どちらでも追加でxのコストが掛かるようにする
辺SvとvTに追加でxのコストを足せばよい
これで負の辺が消える
この操作でオフセットがx増える
この「xを足す」はピッタリxである必要はないのでピッタリが面倒な場合には適当に十分大きな値を出せば良い
ここまでできたらDinicなどのアルゴリズムでスタートからゴールまでの最大流fをもとめる
コストを容量と読み替えれば良い
offset - f が求める答え
---
でもどうせならatcoderで解ける問題がいいな
+4 AOJ