Description

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

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

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

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

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

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

Input Format

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

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

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

Output Format

3 3
1 2 3
1 3 2
2 3 5

2

Hint

【样例解释】

有三种可能，

如果(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

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct sdu{
	long long x,y,z;
}edge[200200];
long long f[200200],sz[200200],n,m,tot=0,ans=0;
bool cmp(sdu b,sdu c){
	return b.z<c.z;
}
int found(long long x){
	if(f[x]==x)return x;
	return f[x]=found(f[x]);
}
int main(){
	
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%lld%lld%lld",&edge[i].x,&edge[i].y,&edge[i].z);
	sort(edge+1,edge+1+m,cmp);
	for(long long i=1;i<=n;i++)f[i]=i,sz[i]=1;
	for(long long i=1;i<=m;i++){
		long long fx=found(edge[i].x);
		long long fy=found(edge[i].y);
		if(fx==fy)continue;
		ans+=sz[fx]*sz[fy]*edge[i].z;
		tot+=edge[i].z;
		sz[fx]+=sz[fy];
		f[fy]=fx;
	}
	printf("%.0lf",tot-ans*2.0/n/(n-1));
	return 0;
} 

Source