A5808 | $「NOI2012」迷失游乐园$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

放假了，小 Z 觉得呆在家里特别无聊，于是决定一个人去游乐园玩。进入游乐园后，小 Z 看了看游乐园的地图,发现可以将游乐园抽象成**有 $n$ 个景点、$m$ 条道路的无向连通图，且该图中至多有一个环（即 $m$ 只可能等于 $n$ 或者 $n-1$）**。 小 Z 现在所在的大门也正好是一个景点。小 Z 不知道什么好玩，于是他决定，从当前位置出发，每次随机去一个和当前景点有道路相连的景点，并且**同一个景点不去两次（包括起始景点）**。贪玩的小 Z 会一直游玩，直到当前景点的相邻景点都已经访问过为止。 小 Z 所有经过的景点按顺序构成一条非重复路径，他想知道这条路径的**期望长度**是多少？ 小 Z 把游乐园的抽象地图画下来带回了家，可是忘了标哪个点是大门，他只好假设每个景点都可能是大门（即每个景点作为起始点的概率是一样的）。同时，他每次在选择下一个景点时会**等概率地随机**选择一个**还没去过的相邻景点**。

第一行是两个整数 $n$ 和 $m$，分别表示景点数和道路数。 接下来 $m$ 行，每行三个整数 $X_i , Y_i , W_i$，分别表示第 $i$ 条路径的两个景点为 $X_i , Y_i$，路径长 $W_i$。所有景点的编号从 $1$ 至 $n$，两个景点之间至多只有一条道路。

共一行，包含一个实数，即路径的期望长度。

输入 #1

输出 #1

6.00000000

C++ 编辑器

输入

输出