BZOJ 3036 绿豆蛙的归宿

发布于 2017-06-12  147 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3036

题意:一个 DAG,从 1 出发,每次随机沿着一个方向走出去,问走到 N 的期望长度...


$$f_i=\frac{\sum_{j\in son_i}^{ }f_j+dis(i,j)}{deg_i}$$

于是按照拓扑序倒着来即可,dfs 回溯时完成...

 


一个非常弱的准退役OIER