最小費用流に帰着

https://gyazo.com/4b7d4a231225f9f2363bf0e692829b53

記法を整理して色々な問題のフローを描いてみる

各論

https://gyazo.com/38dcd4abb0b8f661eb30039f293a802c

3箇所に石がXi個置かれている

これを不特定個のマスに最大1個ずつ割り振る

問題条件としては無限個だが、現実的にはXiの和くらいの数で十分

コストCijは置かれてる場所から目的地への距離

https://gyazo.com/c243561fb3069ff0f7a2c41046325ef2

https://gyazo.com/11af29d8073e126040a8d77a4f22b2d8

3回のラウンドで、それぞれM個のものをN個の場所に割り当てる

この時、報酬Rijが得られる

ただし最終的に場所jに何個割り当てられていたかkによってコストDjkが掛かる

このコストは累進である

なのでCjk=Djk-Dj(k-1)を使って表現できる

安い方から選ばれるので

https://gyazo.com/eaaba4778f81bf4f4751b1e923ffae74

同じ列には最大K個まで

=N個の場所から最大K個選ぶ

ちょうどK個ではないのが重要

脇道を作ることで選ばない選択を認める

マス目が二部グラフの辺に対応する

https://gyazo.com/92ae403683bc716bc08c1a73ec2e8528

得られる報酬が最大のもののうちコストが最小なものを選ぶ

選択肢はM、選ばれる個数L=min(N, M)

報酬は辺に乗せるのではなくグラフの構築に使う

報酬Rjの大きい順にソートし、L番目と同点のB個から、それより点の高い確定で選ぶ個数をAとして、残りのL-A個を選ぶ

無向グラフ

頂点1からNに行って1に戻る最短経路

同じ辺を2回通れる

1回目のコストci、2回目のコストdi、di>=ci

https://gyazo.com/0ab440e908ffd90d188962117aa3ec02

流量2を流す

なぜこれでいいのか

https://gyazo.com/671dddb208ffc7a1f3033431de840421

辺を1回だけ通ってる場合には、逆方向にも同じコストで通れる

2回通ってる時には逆辺が消えてるのでコストdになる

流量2を通してコストを2で割れば求めたいものが求まる

関連