🪴 Quartz 4.0

Search

SearchSearch

最小カットに帰着

Dec 01, 2023, 6 min read

問題リスト

  • ✅ARC074D F - Lotus Leaves 難易度: 2208

  • KUPC2016E E - 柵 難易度:不明

  • ✅ABC193F F - Zebraness 難易度:2475 AC

  • ✅ARC085E E - MUL 難易度:2571 AC

  • ARC031D D - 買い物上手 難易度: 2825 考察OK

  • ARC107F F - Sum of Abs 難易度: 3130 考察OK

  • WUPC2019F F - RPG 難易度:不明 考察OK

  • 💻KUPC2017H H - Make a Potion 難易度:不明　整数値

  • TTPC2015L L - グラフ色ぬり 難易度:不明

  • 最適な選択を見つける問題

    • 典型的なパターン

      • 100×100のグリッドを二色で塗り分ける
      • 2択の選択肢が100個くらいある
        • その選択によってコストや報酬が発生する
        • 選択の間に依存関係がある

    • 選択を頂点の二色の塗りで表現する

    • この塗りの色をSとTと呼ぶ

    • 2つの頂点スタートとゴールを導入する

      • これはそれぞれSとTで塗られている
      • この頂点自体をSとTと表現することもある、ぼくはコード上はstartとgoalで、図に書く時にSとT

    • 二択の選択肢なら自然に対応する

    • 三択以上でも表現できる ARC107F

  • 最小カットに帰着する上では「辺の両端の色が違えばコスト発生」「コストを最小化したい」が基本形

    • 頂点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 が求める答え

最小カットのカットは「辺を切る」ではないに気づいたことでもう少し整理できそうな気がしてきた

Graph View

Backlinks