ABC144 F - Fork in the Road
問題
$ N頂点$ 0, 1, \dots , N-1
$ M辺$ (s_0, t_0), (s_1, t_1), \dots, (s_{M-1}, t_{M-1})
頂点$ 0から、辺で繋がった頂点へランダムに移動することを繰り返します。
頂点$ N-1に達するまでの移動回数の期待値を$ Eとします。
$ Eを最小化するように辺を1つ取り除いたときの$ Eの値を求めてください。
ただし、辺を取り除くことで$ N - 1に移動できなくなる辺は選べません。
制約
$ 2 \leq N \leq 600
$ N - 1 \leq M \leq \frac{N(N-1)}{2}
頂点$ s_iから頂点$ t_iへの有向辺が与えられる
$ s_i \lt t_i
$ i \neq jのとき$ (s_i, t_i) \neq (s_j, t_j)
任意の$ v = 0,2, \dots , N - 2に対し、ある$ iが存在して$ v = s_i
解答
頂点$ iから頂点$ N-1に至る移動回数の期待値を$ E_iとします。
このとき、以下が成立します。
$ E_i = \frac{1}{n^{out}_i} \sum_{辺(i,j)} E_j + 1
ここで$ n^{out}_iは$ iの出自数です。
もし、辺を取り除かない場合には$ E_0は$ O(M)で計算できます。
愚直に、辺を1つ1つ取り除いて$ E_0を再計算して、とすると$ O(M^2)で間に合いません。
ある辺を取り除いた時に、$ E_0がどれだけ変化するかを効率よく出すことはできないでしょうか?
辺$ u \rightarrow vを取り除くと考えます。取り除いた後の$ uから$ N - 1までの移動回数の期待値を$ E'_uとすると、
$ n^{out}_u = 1のときは、$ uから$ N - 1にたどり着けなくなるので
$ E'_u = 0
$ n^{out}_u \neq 1のときは
$ E'_u = \frac{1}{n^{out}_u - 1} (\sum_{辺(u,w)} E_w - E_v) = \frac{n^{out}_u}{n^{out}_u - 1} E_u - \frac{n^{out}_u}{n^{out}_u - 1} - \frac{E_v}{n^{out}_u - 1} + 1 = \frac{1}{n^{out}_u - 1} (n^{out}_u E_u - E_v - 1)
となります。
したがって、$ E_uの変化量$ \Delta E_u = E'_u - E_uは
$ n^{out}_u = 1のとき
$ \Delta E_u = - E_u
$ n^{out}_u \neq 1のとき
$ \Delta E_u = \frac{1}{n^{out}_u - 1} (E_u - E_v - 1)
です。
各$ E_iは、移動していく先の期待値にのみ依存しているので、$ uより$ N - 1に近い部分の期待値は変化しません。$ 0に近い部分の期待値は$ E'_uの変化によって変化します。
各$ E_iは移動先の$ E_jの線形和で書けているので、$ E_iの漸化式を繰り返し用いることで$ E_0は独立したパス上の頂点達の$ E_iの線形和で表せるはずです。このように表したときの係数を$ C_iとします。$ C_iは$ E_iが$ E_0へどれだけ寄与しているかを表す量です。
このとき
$ \Delta E_0 = C_u \Delta E_u
となります。
$ E_iの漸化式より
$ C_u = \sum_{辺(w,u)} \frac{1}{n^{out}_w} C_w
となります。
$ C_u = 1で$ n^{out}_u = 1な$ uは、取り除くと$ N-1に到達できなくなるので取り除けません。
以上のことから、$ O(M)で、すべての$ iについて$ E_i, C_iを事前に計算しておくことで、変化量の計算は$ O(1)で行えることがわかりました。したがって、辺すべてについて試すことで$ O(M)で答えを求めることができます。