【问题描述】
你和你的好朋友小山正在讨论老师今天上午刚讲的知识点——最小生成树。 你们两个都觉得自己算最小生成树的速度最快,于是你们就用电脑生成了一张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