luogu#P2081. [NOI2012] 迷失游乐园

    ID: 6129 远端评测题 1000ms 500MiB 尝试: 3 已通过: 2 难度: 6 上传者: 标签>动态规划dp图论递推2012NOI 系列Special Judge期望

[NOI2012] 迷失游乐园

题目描述

放假了,小 Z 觉得呆在家里特别无聊,于是决定一个人去游乐园玩。

进入游乐园后,小 Z 看了看游乐园的地图,发现可以将游乐园抽象成有 nn 个景点、mm 条道路的无向连通图,且该图中至多有一个环(即 mm 只可能等于 nn 或者 n1n-1)。

小 Z 现在所在的大门也正好是一个景点。小 Z 不知道什么好玩,于是他决定,从当前位置出发,每次随机去一个和当前景点有道路相连的景点,并且同一个景点不去两次(包括起始景点)。贪玩的小 Z 会一直游玩,直到当前景点的相邻景点都已经访问过为止。

小 Z 所有经过的景点按顺序构成一条非重复路径,他想知道这条路径的期望长度是多少?

小 Z 把游乐园的抽象地图画下来带回了家,可是忘了标哪个点是大门,他只好假设每个景点都可能是大门(即每个景点作为起始点的概率是一样的)。同时,他每次在选择下一个景点时会等概率地随机选择一个还没去过的相邻景点。

输入格式

第一行是两个整数 nnmm ,分别表示景点数和道路数。

接下来 mm 行,每行三个整数 Xi,Yi,WiX_i, Y_i, W_i,分别表示第 ii 条路径的两个景点为 Xi,YiX_i, Y_i,路径长 WiW_i。所有景点的编号从 11nn,两个景点之间至多只有一条道路。

输出格式

共一行,包含一个实数,即路径的期望长度,保留五位小数。

4 3
1 2 3
2 3 1
3 4 4
6.00000000

提示

样例解释

样例数据中共有 66 条不同的路径:

路径 长度 概率
141\rightarrow 4 88 14\frac{1}{4}
212\rightarrow 1 33 18\frac{1}{8}
242\rightarrow 4 55
313\rightarrow 1 44
343\rightarrow 4
414\rightarrow 1 88 14\frac{1}{4}

因此期望长度 $= \frac{8}{4} + \frac{3}{8} + \frac{5}{8} +\frac{4}{8} + \frac{4}{8} +\frac{8}{4} = 6.00$

评分方法

本题没有部分分,你程序的输出只有和标准答案的差距不超过 0.010.01 时,才能获得该测试点的满分,否则不得分。

数据规模和约定

对于 100%100\% 的数据,1Wi1001\leq W_i\leq 100

测试点编号 nn mm 备注
11 n=10n=10 m=n1m = n-1 保证图是链状
22 n=100n=100 只有节点 11 的度数大于 22
33 n=1000n=1000 /
44 n=105n=10^5
55
66 n=10n=10 m=nm = n
77 n=100n=100 环中节点个数 5\leq 5
88 n=1000n=1000 环中节点个数 10\leq 10
99 n=105n=10^5 环中节点个数 15\leq 15
1010 环中节点个数 20\leq 20