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

各論

ABC004D D - マーブル

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

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

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

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

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

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

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

このコストは累進である

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

安い方から選ばれるので

同じ列には最大K個まで

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

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

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

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

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

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

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

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

無向グラフ

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

同じ辺を2回通れる

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

流量2を流す

なぜこれでいいのか

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

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

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

関連

グラフの最短経路問題に帰着するのも仲間かもしれない