HDU 5723 Abandoned country (最小生成树+dfs)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5723

n个村庄m条双向路，从中要选一些路重建使得村庄直接或间接相连且花费最少，这个问题就是很明显的求最小生成树，由于边权各不相同，所以最小生成树唯一。

然后，在这个最小生成树的基础上，求各个路径的最小期望和（推导出期望 = 所有村庄中任意两个村庄距离之和 / 村庄对数）。

最小生成树很好求(边权从小到大，并查集一下就好了)。

然后求以上基础村庄中任意两个村庄距离之和，只要求每条边乘上每条边出现的次数，每条边出现的次数通过观察看出是u相连点个数乘上v相连点个数。这个dfs一遍就可以求。

最后除以村庄对数就好了。

 1 //#pragma comment(linker, "/STACK:102400000, 102400000")
 2 #include <algorithm>
 3 #include <iostream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <vector>
 8 #include <cmath>
 9 #include <ctime>
10 #include <list>
11 #include <set>
12 #include <map>
13 using namespace std;
14 typedef long long LL;
15 typedef pair <int, int> P;
16 const int N = 1e5 + 5;
17 int par[N] , num[N]; //num[i]表示以i为根的子树的点个数
18 vector <P> G[N]; //树的各条边
19 vector <P> edge[N*10]; //边权为下标
20 
21 void init(int n) {
22     for(int i = 1 ; i <= n ; ++i) {
23         par[i] = i;
24         num[i] = 0;
25         G[i].clear();
26     }
27     for(int i = 1 ; i <= 1000000 ; ++i)
28         edge[i].clear();
29 }
30 
31 int Find(int n) {
32     if(n == par[n])
33         return n;
34     return par[n] = Find(par[n]);
35 }
36 
37 int dfs(int u , int pre) { //生成树dfs
38     num[u] = 1;
39     for(int i = 0 ; i < G[u].size() ; ++i) {
40         P temp = G[u][i];
41         if(temp.first == pre)
42             continue;
43         num[u] += dfs(temp.first , u);
44     }
45     return num[u];
46 }
47 
48 LL dfs2(int u , int pre) {
49     LL res = 0;
50     for(int i = 0 ; i < G[u].size() ; ++i) {
51         P temp = G[u][i];
52         if(temp.first == pre)
53             continue;
54         res += dfs2(temp.first , u);
55         res += (LL)temp.second * (LL)(num[1] - num[temp.first]) * (LL)num[temp.first];
56     }
57     return res;
58 }
59 
60 int main()
61 {
62     int t , n , m , u , v , w;
63     scanf("%d" , &t);
64     while(t--) {
65         scanf("%d %d" , &n , &m);
66         init(n);
67         for(int i = 0 ; i < m ; ++i) {
68             scanf("%d %d %d" , &u , &v , &w);
69             edge[w].push_back(P(u , v));
70         }
71         LL sum = 0; //最小生成树权值
72         int cnt = n; //集合数
73         for(int i = 1 ; i <= 1000000 ; ++i) {
74             if(cnt == 1)
75                 break;
76             if(!edge[i].size()) //因为每条边权值不同 所以每条边对应只有一对点
77                 continue;
78             int faru = Find(edge[i][0].first) , farv = Find(edge[i][0].second);
79             if(farv == faru)
80                 continue;
81             par[faru] = farv;
82             sum += (LL)i;
83             G[edge[i][0].first].push_back(P(edge[i][0].second , i));
84             G[edge[i][0].second].push_back(P(edge[i][0].first , i));
85         }
86         dfs(1 , -1);
87         LL res = dfs2(1 , -1); //村庄距离之和
88         LL cont = (LL)n * (LL)(n - 1) / 2; //村庄对数
89         printf("%lld %.2f
" , sum , res * 1.0 / cont);
90     }
91     return 0;
92 }