Boxes (SPOJ 371)

http://www.spoj.pl/problems/BOXES/

問題

n個の箱が円形にならんでいる。各箱にはki個のボールが入っている。ボールを箱から一つ取り出して隣の箱に入れる操作のみが行える。全ての箱に1個以下のボールが入っている状態にするためには何回操作を行わないといけないか求めよ。
1<=n<=1000
kiの合計はn以下

解法

各ボールをどこの箱に入れるかは割当問題なので最小費用流で解ける。そのままグラフを作って最小費用流を使うとO(n^3logn)程度かかるのでグラフの構築を工夫しないといけない。ここである箱のボールを移動させる場合は、空箱にたどり着くまでの間に入ってるボールを優先的に入れることにする。こうすることで辺の数がO(n)で抑えることが出来てO(n^2logn)で解ける。
追記：高速に解けるらしい。