AOJ 3058 - Ghost (RUPC2019 Day2 H) - ツバサの備忘録

解法

燃やす埋める問題です。
詳しくはこちらを。
始点と終点 $s,t$ および各幽霊に対応する作り、 $s$ から各幽霊、各幽霊から $t$ に辺をはります。
この際、 $s$ から出てくる辺を左に向くパターン、 $t$ へ向かう辺を右に向くパターンとすると、
今 $i$ 番目の幽霊が向いている向きが

右のとき
$s$ から出てくる辺は容量 $A_{i}$ 、 $t$ へ向かう辺は容量 $0$
左のとき
$s$ から出てくる辺は容量 $0$ 、 $t$ へ向かう辺は容量 $A_{i}$

となるように辺をはればよいです。
そして、 $i$ 番目と $j$ 番目の幽霊が向かい合っているときに $B$ の恐怖度が発生するとしたとき( $i \lt j$ とします)、
$i$ から $j$ に容量 $B$ の辺をはると、うまく条件を表現することができます。
あとは、フローを流していき、最小カットを求めれば答えとなります。

感想

問題を見た時点で燃やす埋める問題だ！となったので、成長を感じます。
こういう気づけばあとはコピペで終わるような問題をさらっと解けるようになると気持ちいいですね。