1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 typedef pair<int,int> pll;
14 const int INF = 0x3f3f3f3f;
15 const int maxn = 100000 + 5;
16 
17 int n, m;
18 double tot;
19 
20 struct node
21 {
22     int u,v,w;
23     bool operator< (const node& rhs) const
24     {
25         return w<rhs.w;
26     }
27 }edge[1000005];
28 
29 int p[maxn];
30 vector<pll> G[maxn];
31 
32 int Find(int x)
33 {
34     return p[x]==x?x:p[x]=Find(p[x]);
35 }
36 
37 void Kruskal()
38 {
39     ll sum = 0;
40     int num=0;
41     sort(edge,edge+m);
42     for(int i=0;i<m;i++)
43     {
44         int x = Find(edge[i].u);
45         int y = Find(edge[i].v);
46         if(x!=y)
47         {
48             p[x]=y;
49             sum+=edge[i].w;
50             num++;
51             G[edge[i].u].push_back(make_pair(edge[i].v,edge[i].w));
52             G[edge[i].v].push_back(make_pair(edge[i].u,edge[i].w));
53         }
54         if(num==n-1)  break;
55     }
56     printf("%I64d ",sum);
57 }
58 
59 
60 int dfs(int u, int fa)
61 {
62     int cnt = 0;
63     for(int i=0;i<G[u].size();i++)
64     {
65         int v = G[u][i].first;
66         int w = G[u][i].second;
67         if(v==fa)  continue;
68         int now = dfs(v, u);
69         cnt += now;
70         tot += 1.0 * now * (n - now) * w;
71     }
72     return cnt+1;
73 }
74 
75 int main()
76 {
77     //freopen("in.txt","r",stdin);
78     int T;
79     scanf("%d",&T);
80     while(T--)
81     {
82         scanf("%d%d",&n,&m);
83         for(int i=0;i<=n;i++)  {p[i]=i;G[i].clear();}
84         for(int i=0;i<m;i++)
85         {
86             scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
87         }
88         Kruskal();
89         tot=0;
90         dfs(1,-1);
91         printf("%.2f\n",tot*2.0/(1.0*n)/(n-1.0));
92     }
93     return 0;
94 }

优质内容筛选与推荐>>
1、2018-07-30 对DLL库中的接口进行中文命名
2、全景影像（360°环视）系统发展历程
3、【ODI】| 数据ETL：从零开始使用Oracle ODI完成数据集成（二）
4、Navicat破解版（蔡军帅亲测可用）
5、UML图