HDU 5723 Abandoned country（落后渣国）

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Description

题目描述

An abandoned country has n(n≤100000) villages which are numbered from 1 to n. Since abandoned for a long time, the roads need to be re-built. There are m(m≤1000000) roads to be re-built, the length of each road is wi(wi≤1000000). Guaranteed that any two wi are different. The roads made all the villages connected directly or indirectly before destroyed. Every road will cost the same value of its length to rebuild. The king wants to use the minimum cost to make all the villages connected with each other directly or indirectly. After the roads are re-built, the king asks a men as messenger. The king will select any two different points as starting point or the destination with the same probability. Now the king asks you to tell him the minimum cost and the minimum expectations length the messenger will walk.

一个落后渣国有n(n≤100000)座从1到n编号的村子。荒废久了，路也该重新修修。有m(m≤1000000)条路需要重建，每条路长wi(wi≤1000000)。每条路长wi各不相同。旧时的路使村子直接或间接连通。每条路重修的单位造价相同。国王希望花最少的钱使各个村子直接或间接连通。待到这些路重修好后，国王会物色一个信使。国王会等概率地选择两个点作为起点和终点。现在国王想问你这个工程的最低造价与信使所走过路程的期望。

Input

输入

The first line contains an integer T(T≤10) which indicates the number of test cases.

For each test case, the first line contains two integers n,m indicate the number of villages and the number of roads to be re-built. Next m lines, each line have three number i,j,wi, the length of a road connecting the village i and the village j is wi.

第一行是一个整数T(T≤10)表示测试用例的数量。

对于每个测试用例，第一行有两个整数n，m表示村子与待重修路的数量。接下来m行，每行有三个数i，j，wi，表示有一条长wi的路连接村子i与j。

Output	输出
output the minimum cost and minimum Expectations with two decimal places. They separated by a space.	输出最低造价与保留两位小数的最小期望。用一个空格分开。

Sample Input - 输入样例	Sample Output - 输出样例
1 4 6 1 2 1 2 3 2 3 4 3 4 1 4 1 3 5 2 4 6	6 3.33

【题解】

　　最小生成树+求期望，注意越界。

　　　　期望 = 总路程/方法数。

　　　　总路程分散到每条路上求，每条路经过的距离=长度*上方节点数*下方节点数。DFS可轻松求下方节点数，因此，上方节点数=n-下方节点数。

　　　　方法数=1+2+……+(n-1)，即n*(n-1)/2。

【代码 C++】

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 int n, m, link[100005], head[100005], iE;
 5 __int64 fCost, sum, cnt;
 6 struct Edge{
 7     int to, next, len;
 8 }edge[200005];
 9 void addEdge(int u, int v, int len){
10     edge[iE].to = v; edge[iE].len = len; edge[iE].next = head[u];
11     head[u] = iE++;
12 }
13 struct Road{
14     int a, b, len;
15     bool operator<(const Road &r) const{
16         return len < r.len;
17     }
18 }iRoad[1000005];
19 int fid(int a){
20     return link[a] == a ? a : link[a] = fid(link[a]);
21 }
22 bool beCnct(int a, int b){
23     if (a == b) return 0;
24     return link[a] = b;
25 }
26 void build(){
27     int i, j, u, v, len;
28     for (i = 1; i <= n; ++i) link[i] = i;
29     fCost = iE = 0; memset(head, -1, sizeof(head));
30 
31     for (i = 0; i < m; ++i) scanf("%d%d%d", &iRoad[i].a, &iRoad[i].b, &iRoad[i].len);
32     std::sort(iRoad, iRoad + m);
33 
34     for (i = 0, j = 1; j < n; ++i){
35         u = iRoad[i].a; v = iRoad[i].b; len = iRoad[i].len;
36         if (beCnct(fid(u), fid(v))){
37             addEdge(u, v, len); addEdge(v, u, len);
38             fCost += len; ++j;
39         }
40     }
41     cnt = (__int64)n*(n - 1) >> 1;
42 }
43 
44 __int64 DFS(int now, int pre){
45     int i;
46     __int64 opt = 1, temp;
47     for (i = head[now]; ~i; i = edge[i].next){
48         if (i == pre) continue;
49         opt += temp = DFS(edge[i].to, i ^ 1);
50         sum += temp*(n - temp)*edge[i].len;
51     }
52     return opt;
53 }
54 int main(){
55     int t;
56     scanf("%d", &t);
57     while (t--){
58         scanf("%d%d", &n, &m);
59         build();
60         sum = 0;  DFS(1, -1);
61         printf("%I64d %.2lf
", fCost, 1.0*sum / cnt);
62     }
63     return 0;
64 }