オンサイトで未確認

ukuku09の活動記録。

AOJ 0293: Algorithm Exam

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?lang=jp&id=0293

 

解法

割り当てとか言われたらフローを流したくなるわけだけど、やっぱり最小費用流。

 

会場の使い方は最悪でも 2^5 通りなので、全部試す。

次に考えるべきは、バスの距離 $D$ が決まっている場合。受験者 $i$ の家と会場 $j$ との距離は $max(0, |ax_i - bx_j| + |ay_i - by_j| - D)$ で求まるので、このコストの辺を受験者と会場の間に張る。あとはソースからすべての受験者に向けて容量 1 の辺を、会場 $j$ から容量 $c_j$ の辺をシンクに張ってやると、流量 N を流してあとちょっと計算すれば答えが求まる。

で、その $D$ の決め方だが、これは二分探索で頑張る。

  • 使用する会場を決めたとき、D=i におけるそれらの会場への受験者の割り当て方のうち移動補助金が最小となるときの金額を F(i) とする。このとき、F(i+2) - F(i+1) ≥ F(i+1)-F(i) が成立する。

とかいうよくわからんことが書いてあるが、要は距離 $D$ のときと $D-1$ のときの経費の大小関係で二分探索が使えるということ(だと思う)。

フローを流しまくるので心配になったが、フローは速いのでなんとかなるっぽい。