HDU 1875 畅通工程再续

http://acm.hdu.edu.cn/showproblem.php?pid=1875

题意：

相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在政府决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，政府决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。

思路：

又是畅通工程的题目，用来熟悉最小生成树的不错题目。

 1 #include<iostream> 
 2 #include<cstring>
 3 #include<string>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<cmath>
 7 using namespace std;
 8 
 9 int n, cnt;
10 double ans;
11 int x[105], y[105];
12 int num;
13 
14 struct node
15 {
16     int u;
17     int v;
18     double dist;
19 }edge[105*105];
20 
21 int p[105];
22 
23 double cacl(int x1, int y1, int x2, int y2)
24 {
25     return sqrt((y2 - y1)*(y2 - y1) + (x2 - x1)*(x2 - x1));
26 }
27 
28 int find(int x)
29 {
30     return p[x] == x ? x : find(p[x]);
31 }
32 
33 bool cmp(node a, node b)
34 {
35     return a.dist < b.dist;
36 }
37 
38 void Kruskal()
39 {
40     num = 0;
41     for (int i = 0; i < cnt; i++)
42     {
43         int x = find(edge[i].u);
44         int y = find(edge[i].v);
45         if (x != y)
46         {
47             p[x] = y;
48             ans += edge[i].dist * 100;
49             num++;
50             if (num == n - 1)    return;
51         }
52     }
53 }
54 
55 int main()
56 {
57     //freopen("D:\txt.txt", "r", stdin);
58     int T;
59     scanf("%d", &T);
60     while (T--)
61     {
62         scanf("%d", &n);
63         for (int i = 0; i <= n; i++)
64             p[i] = i;
65 
66         for (int i = 0; i < n; i++)
67             scanf("%d%d", &x[i], &y[i]);
68         cnt = 0;
69         for (int i = 0; i < n; i++)
70         for (int j = i+1; j < n; j++)
71         {
72             double len=cacl(x[i], y[i], x[j], y[j]);
73             if (len >= 10 && len <= 1000)
74             {
75                 edge[cnt].u = i;
76                 edge[cnt].v = j;
77                 edge[cnt].dist = len;
78                 cnt++;
79             }
80         }
81         sort(edge, edge + cnt, cmp);
82         ans = 0;
83         Kruskal();
84         if (num == n - 1)  printf("%.1f
", ans);
85         else   printf("oh!
");
86     }
87 }