M_sea的博客

M_sea的博客

A Mengbier

题解 P4745 【[CERC2017]Gambling Guide】

posted on 2019-04-12 21:20:22 | under 题解 |

设 $f[x]$ 表示从 $x$ 走到 $n$ 的期望步数。

显然有 $\large f[u] = \frac{\sum\limits_{(u,v)\in E}\min(f[u] , f[v])}{deg[u]} + 1$ 。

显然,如果 $f[v]<f[u]$ 就会有贡献,于是可以跑 $\mathrm{dijkstra}$ 。

但是这样子不太好算。把式子变形一下,变为 $\large f[u]= \frac{deg[u] + \sum\limits_{(u,v) \in E} \big[f[v]<f[u]\big]f[v]}{\sum\limits_{(u,v) \in E} \big[f[v] < f[u]\big]}$ 。这样子就可以在 $\mathrm{dijkstra}$ 时直接算出 $f$ 了。

至于正确性?意会一下即可 可以看 神仙 $\mathrm{\color{black}{p}\color{red}{sj}}$ 的 $\mathrm{blog}$

具体实现和细节见代码