Logo CSP.ac

CSP.ac

1 s / 256 MB

#123. 【冬令营】Day2T3-最小生成树

统计

【问题描述】

你和你的好朋友小山正在讨论老师今天上午刚讲的知识点——最小生成树。 你们两个都觉得自己算最小生成树的速度最快,于是你们就用电脑生成了一张n个点m条边的联通图(m>=n-1),

为了满足你们两个的强迫症,这个图中的每条边都不一样长。

于是你们两个开始比较手算生成树的速度。

结果你们两个同时完成了!

在你打算和小山再比较一场时,小山突然对最小生成树失去了兴趣,他问你:“欸,如果我把这个图中随机一条边长度变成0,你说这个图的最小生成树边权和的期望是多少?”

你一下子被问倒了,可是你的自尊心告诉你绝对不能说你不知道。所以你最好快点想个算法出来解决了这个问题。

【输入格式】

第一行两个数n、m,点的编号1~n

接下来m行,每行三个数x、y、z,表示x、y之间有边,z表示长度。

保证所有z各不相同。保证初始图一定是连通图。

【输出格式】

输出一个整数,即答案。(期望不一定是个整数,但是这里默认保留0位小鼠即可)

【样例输入】

3 3
1 2 3
1 3 2
2 3 5

【样例输出】

2

【样例解释】

有三种可能,

如果(2,3)长度变成0,那么最小生成树2+0 = 2

如果(1,3)长度变成0,那么最小生成树3+0 = 3

如果(2,3)长度变成0,那么最小生成树2+0 = 2

最后答案为 (2 + 3 + 2) / 3 = 2.3333333

保留0位小数即2

【数据规模和约定】

对于20%的数据, n<=100

对于60%的数据, n<=1000

对于100%的数据, n<=20000,m<=100000,每条边边权的长度<=1134567