http://acm.split.hdu.edu.cn/showproblem.php?pid=5723
題意：
給出一個無向圖，每條路都有一個代價，求出把所有城市連通的最小代價。在此基礎上，國王會從這裡面随機挑出兩個城市作為起點和終點，求出國王要走的路的期望值。
思路：
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 }