KUPC 2014 I - Rain

• 問題
• AC

合計雨量の差にしか興味がないので、費用$d_i$を使って呪文$i$を唱えると地域$b_i$の雨量が$1$減り地域$a_i$の雨量が$1$増える、つまり雨量が$1$移動するとだけ考えればよい。雨量の移動を自由に繰り返して最小コストで雨量を平準化するのは、最小費用流問題そのものである。

最初の雨量はどの地域も$0$とし、呪文$c_1, ..., c_M$を唱えて雨量が$p_1, ..., p_K$になったとする。グラフは次のように作ればよい:

• $p_v>0$なら、始点$S$から$v$に容量$p_v$、コスト$0$の辺を張る。
• $p_v<0$なら、$v$から終点$T$に容量$-p_v$、コスト$0$の辺を張る。
• 各$b_i$から$a_i$に容量$\infty$、コスト$d_i$の辺を張る。

$S$の出容量のぶんだけ$T$に流したときの最小コストが答えであり、必要な量を流せない場合は$-1$である。計算量（の一例）は${O}(KE \log V)$。