BZOJ 3036 绿豆蛙的归宿


题目链接: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 回溯时完成...

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3036 绿豆蛙的归宿


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,