这篇帖子主要解释为什么正推和倒推有区别,如果想询问做法,请移步至洛谷题解区
倒推:\(dp_i\)表示从\(i \rightarrow n\)的期望距离,\(deg_u\)表示\(u\)点出度
\[dp_u = \sum_{(u,v,w) \in E}{\frac{dp_v + w}{deg_u}} \]正推:\(dp_i\)表示从\(1 \rightarrow i\)的期望距离,\(g_i\)表示\(1 \rightarrow i\)的概率,\(deg_u\)定义同上
\[dp_u = \sum_{(v,u,w) \in E}{\frac{(dp_v + w) \times g_v}{deg_v}} \]解释一下为什么正推会乘上一个系数\(g_v\)
倒推:
\[\begin{align} E(v) &= \sum{p_i x_i} \\ E(u) &= \sum{p_i (x_i + w)} \\ &= \sum{p_i x_i} + \sum{p_i w} \\ &= E(v) + w \end{align} \]因为从\(i\)走到\(n\)的概率之和为1
正推:
\[\begin{align} E(u) &= \sum{p_i x_i} \\ E(v) &= \sum{p_i (x_i + w)} \\ &= \sum{p_i x_i} + \sum{p_i w} \\ &\neq E(v) + w \end{align} \]