HDU 2988 Dark roads （裸的最小生成树）

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

解题报告：一个裸的最小生成树，没看题，只知道结果是用所有道路的总长度减去最小生成树的长度和。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 200000;
 7 int far[maxn+5];
 8 struct node
 9 {
10     int front,rear,length;
11 }lode[maxn+5];
12 
13 int find(int n)
14 {
15     return far[n] == n? n:far[n] = find(far[n]);
16 }
17 bool cmp(node a,node b)
18 {
19     return a.length <= b.length;
20 }
21 int main()
22 {
23     int n,m;
24     while(scanf("%d%d",&n,&m),n||m)
25     {
26         int sum = 0;
27         for(int i = 0; i < m;++i)
28         {
29             scanf("%d%d%d",&lode[i].front,&lode[i].rear,&lode[i].length);
30             sum += lode[i].length;
31         }
32         for(int i = 0;i <= n;++i)  //&sup3;&otilde;&Ecirc;&frac14;&raquo;&macr;&sup2;&cent;&sup2;é&frac14;&macr;
33         far[i] = i;
34         int tot = 0;
35         sort(lode,lode+m,cmp);
36         for(int i = 0;i < m;++i)
37         {
38             int temp1 = find(lode[i].front);
39             int temp2 = find(lode[i].rear);
40             if(temp1 != temp2)
41             {
42                 far[temp1] = temp2;
43                 tot += lode[i].length;
44             }
45         }
46         printf("%d
",sum - tot);
47     }
48     return 0;
49 }

View Code