题意

给出一个 DAG ,边有边权,求从 \(1\) 到 \(n\) 的期望长度。

分析

利用期望可加性。考虑每一条边对答案的贡献。

用 \(f[x]\) 表示节点 \(x\) 的经过次数在总点数中的比例,那么从 \(x\) 出去的边的贡献为 \(\frac{f[x]}{k_x}\) , \(k_x\) 为节点 \(x\) 的出边总数量。

显然 \(ans=\sum_{(x,y,val_i)\in E} val_i\cdot\frac{f[x]}{k_x}\)  。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注