#P3470. Freda’s Walk

    ID: 2683 传统题 1000ms 512MiB 尝试: 188 已通过: 59 难度: 6 上传者: 标签>难度分类提高图论Kahn 算法动态规划期望 DP概率 DP组合数学贡献法枚举与搜索暴力枚举CF2100Adera2

Freda’s Walk

Freda’s Walk

题目描述

雨后,Freda 和 Rainbow 想在 Poetic Island 散步。岛上的交通是一张有 nn 个点、mm 条有向边的无环图。每条边都有给定的积水深度。

如果他们正位于 uu,且目前从 uu 出发的边的积水深度之和为 ss,就以 ws\frac{w}{s} 的概率选取其中积水深度为 ww 的一条边。到达没有出边的点时,散步结束。散步的路程是经过的边数。

出发前,他们可以决定在整个散步过程中忽略一条有向边,也可以保留所有边。忽略一条边后,选择概率只按仍然存在的边计算。求从 00 号点出发时,散步路程的最大期望。

输入格式

第一行包含两个正整数 n,mn,m,分别表示点数和有向边数。

接下来 mm 行,每行包含三个整数 u,v,wu,v,w,表示一条由 uu 指向 vv、积水深度为 ww 的边。

输出格式

输出一行一个实数,表示最大期望,四舍五入保留六位小数。

样例 #1

4 5
0 1 2
0 2 1
0 3 3
1 3 1
2 3 4
2.000000

数据范围

2≤n≤100002\le n\le 10000,1≤m≤1000001\le m\le 100000,0≤u,v<n0\le u,v<n,1≤w≤10001\le w\le 1000。