题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5723
n个村庄m条双向路，从中要选一些路重建使得村庄直接或间接相连且花费最少，这个问题就是很明显的求最小生成树，由于边权各不相同，所以最小生成树唯一。
然后，在这个最小生成树的基础上，求各个路径的最小期望和（推导出 期望 = 所有村庄中任意两个村庄距离之和 / 村庄对数）。
最小生成树很好求(边权从小到大，并查集一下就好了)。
然后求以上基础村庄中任意两个村庄距离之和，只要求每条边乘上每条边出现的次数，每条边出现的次数通过观察看出是u相连点个数乘上v相连点个数。这个dfs一遍就可以求。
最后除以村庄对数就好了。
//#pragma comment(linker, "/STACK:102400000, 102400000")
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
typedef long long LL;
typedef pair <int, int> P;
const int N = 1e5 + ;
int par[N] , num[N]; //num[i]表示以i为根的子树的点个数
vector <P> G[N]; //树的各条边
vector <P> edge[N*]; //边权为下标 void init(int n) {
for(int i = ; i <= n ; ++i) {
par[i] = i;
num[i] = ;
G[i].clear();
}
for(int i = ; i <= ; ++i)
edge[i].clear();
} int Find(int n) {
if(n == par[n])
return n;
return par[n] = Find(par[n]);
} int dfs(int u , int pre) { //生成树dfs
num[u] = ;
for(int i = ; i < G[u].size() ; ++i) {
P temp = G[u][i];
if(temp.first == pre)
continue;
num[u] += dfs(temp.first , u);
}
return num[u];
} LL dfs2(int u , int pre) {
LL res = ;
for(int i = ; i < G[u].size() ; ++i) {
P temp = G[u][i];
if(temp.first == pre)
continue;
res += dfs2(temp.first , u);
res += (LL)temp.second * (LL)(num[] - num[temp.first]) * (LL)num[temp.first];
}
return res;
} int main()
{
int t , n , m , u , v , w;
scanf("%d" , &t);
while(t--) {
scanf("%d %d" , &n , &m);
init(n);
for(int i = ; i < m ; ++i) {
scanf("%d %d %d" , &u , &v , &w);
edge[w].push_back(P(u , v));
}
LL sum = ; //最小生成树权值
int cnt = n; //集合数
for(int i = ; i <= ; ++i) {
if(cnt == )
break;
if(!edge[i].size()) //因为每条边权值不同 所以每条边对应只有一对点
continue;
int faru = Find(edge[i][].first) , farv = Find(edge[i][].second);
if(farv == faru)
continue;
par[faru] = farv;
sum += (LL)i;
G[edge[i][].first].push_back(P(edge[i][].second , i));
G[edge[i][].second].push_back(P(edge[i][].first , i));
}
dfs( , -);
LL res = dfs2( , -); //村庄距离之和
LL cont = (LL)n * (LL)(n - ) / ; //村庄对数
printf("%lld %.2f\n" , sum , res * 1.0 / cont);
}
return ;
}