【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=5723
【题目大意】
n座城市，m条路径，求解：
1.最短的路径和，使得n座城市之间直接或者间接连通
2.在路径和最短的情况下，求出任意两个城市之间的期望距离
【题解】
对于问题1，只需求出该图的最小生成树，边权和即答案，由于边权值唯一，因此不存在最小生成树多解的情况。
对于问题2，期望的通常求法为(任意两点之间的路径和)/(点对数）
那么问题就转化为任意两点间距离和的问题，我们按边考虑，对于每条树上的边，它对答案的贡献值为左边的点数×右边的点数×边权，搜索每个记录每棵子树的大小，对于子树和父节点相连的这条边，他左右两边的点数分别为（总点数-子树大小）和（子树大小），那么递归计算答案即可。
【代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000005;
int T,n,m,f[N],nxt[N],w[N],v[N],cnt[N],g[N],ed;
double ans1,ans2;
struct data{int x,y,z;}a[N];
bool cmp(data a,data b){return a.z<b.z;}
int sf(int x){return x==f[x]?x:f[x]=sf(f[x]);}
void add(int x,int y,int z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,int pre){
cnt[x]=1;
for(int i=g[x];i;i=nxt[i])if(v[i]!=pre){
dfs(v[i],x);
cnt[x]+=cnt[v[i]];
ans2+=2.0*cnt[v[i]]*(n-cnt[v[i]])*w[i];
}
}
int main(){
scanf("%d",&T);
while(T--){
ans1=ans2=ed=0;
memset(v,0,sizeof(v)); memset(nxt,0,sizeof(nxt));
memset(w,0,sizeof(w)); memset(g,0,sizeof(g));
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++){
if(sf(a[i].x)==sf(a[i].y))continue;
f[sf(a[i].x)]=sf(a[i].y);
ans1+=a[i].z;
add(a[i].x,a[i].y,a[i].z);
add(a[i].y,a[i].x,a[i].z);
}dfs(1,1);
printf("%.0f %.2f\n",ans1,ans2/n/(n-1));
}return 0;
}