hdu 1875 畅通工程再续最小生成树

畅通工程再续

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7266 Accepted Submission(s): 2185

Problem Description

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

Input

输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。

Output

每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.

Sample Input

10 10

20 20

1 1

2 2

1000 1000

Sample Output

1414.2

oh!

代码：

View Code

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <math.h>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 struct e{
 9     int x;
10     int y;
11 }map[1005];
12 struct node{
13     int x;
14     int y;
15     double len;
16 }road[5050];
17 int pre[105];
18 bool flag[5050];
19 
20 int cmp(node a,node b)
21 {
22     return a.len<b.len;
23 }
24 
25 int find(int x)
26 {
27     if(pre[x]!=x)
28         pre[x]=find(pre[x]);
29     return pre[x];
30 }
31 
32 int Union(int a,int b)        //合并两点
33 {
34     int x=find(a);
35     int y=find(b);
36     if(x==y) return 1;
37     else {
38         pre[y]=x;
39         return 0;
40     }
41 }
42 
43 int main()
44 {
45     int n,m,t;
46     int i,j;
47     scanf("%d",&t);
48     while(t--)
49     {
50         scanf("%d",&n);
51         memset(flag,false,sizeof(flag));
52         for(i=0;i<n;i++)
53             pre[i]=i;
54         for(i=0;i<n;i++)
55             scanf("%d%d",&map[i].x,&map[i].y);    //记录每个点坐标
56         int k=0;
57         for(i=0;i<n;i++)
58         {
59             for(j=i+1;j<n;j++)
60             {
61                 road[k].x=i;
62                 road[k].y=j;
63                 road[k].len=sqrt((double)(map[j].y-map[i].y)*(map[j].y-map[i].y)+(double)(map[j].x-map[i].x)*(map[j].x-map[i].x));  //算出每条边的长度
64                 k++;
65             }
66         }
67         double ans=0;
68         int sum=0;
69         sort(road,road+k,cmp);
70         for(i=0;i<k;i++)
71         {
72             if(road[i].len>=10 && road[i].len<=1000)
73             {
74                 if(Union(road[i].x,road[i].y)==0)
75                     ans+=road[i].len;
76             }
77         }
78         for(i=0;i<n;i++)
79             flag[find(i)]=true;
80         for(i=0;i<n;i++)
81         {
82             if(flag[i]==true)
83                 sum++;
84         }
85         if(sum!=1) printf("oh!\n");
86         else printf("%.1lf\n",ans*100);
87     }
88     return 0;
89 }

hdu 1875 畅通工程再续 最小生成树

畅通工程再续

hdu 1875 畅通工程再续最小生成树