最小費用流に帰着
各論
- ABC004D D - マーブル
3箇所に石がXi個置かれている
これを不特定個のマスに最大1個ずつ割り振る
- 問題条件としては無限個だが、現実的にはXiの和くらいの数で十分
コストCijは置かれてる場所から目的地への距離
- PAST3O
3回のラウンドで、それぞれM個のものをN個の場所に割り当てる
この時、報酬Rijが得られる
ただし最終的に場所jに何個割り当てられていたかkによってコストDjkが掛かる
このコストは累進である
なのでCjk=Djk-Dj(k-1)を使って表現できる
- 安い方から選ばれるので
- ACLPC E
- 同じ列には最大K個まで
- =N個の場所から最大K個選ぶ
- ちょうどK個ではないのが重要
- 脇道を作ることで選ばない選択を認める
- 二次元のマス目は二部グラフ
- マス目が二部グラフの辺に対応する
- F - 3人の騎士と1匹の犬
- Maximum-Cup 2013: F - 3人の騎士と1匹の犬 - kmjp's blog
- 得られる報酬が最大のもののうちコストが最小なものを選ぶ
- 選択肢はM、選ばれる個数L=min(N, M)
- 報酬は辺に乗せるのではなくグラフの構築に使う
- 報酬Rjの大きい順にソートし、L番目と同点のB個から、それより点の高い確定で選ぶ個数をAとして、残りのL-A個を選ぶ
- No.1301 Strange Graph Shortest Path - yukicoder
- 無向グラフ
- 頂点1からNに行って1に戻る最短経路
- 同じ辺を2回通れる
- 1回目のコストci、2回目のコストdi、di>=ci
- 流量2を流す
- なぜこれでいいのか
- 辺を1回だけ通ってる場合には、逆方向にも同じコストで通れる
- 2回通ってる時には逆辺が消えてるのでコストdになる
- 流量2を通してコストを2で割れば求めたいものが求まる 関連
- 最小費用流
- 最大流に帰着
- グラフの最短経路問題に帰着するのも仲間かもしれない
