HDOJ1875 畅通工程再续[Prim()算法]

畅通工程再续

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

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

2 2 10 10 20 20 3 1 1 2 2 1000 1000

Sample Output

1414.2 oh!

Author

8600

Source

2008浙大研究生复试热身赛（2）——全真模拟

Recommend

lcy

code:

  1 #include <iostream>   
  2 #include <iomanip>   
  3 #include <fstream>   
  4 #include <sstream>   
  5 #include <algorithm>   
  6 #include <string>   
  7 #include <set>   
  8 #include <utility>   
  9 #include <queue>   
 10 #include <stack>   
 11 #include <list>   
 12 #include <vector>   
 13 #include <cstdio>   
 14 #include <cstdlib>   
 15 #include <cstring>   
 16 #include <cmath>   
 17 #include <ctime>   
 18 #include <ctype.h> 
 19 using namespace std;
 20 
 21 #define MAXN 1005
 22 
 23 int t,c;
 24 double map[MAXN][MAXN];
 25 double dis[MAXN];
 26 int vst[MAXN];
 27 
 28 typedef struct island
 29 {
 30     double x,y;
 31 }Island;
 32 Island island[MAXN];
 33 
 34 double fun_dis(double x1,double y1,double x2,double y2)
 35 {
 36     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 37 }
 38 
 39 double prim()
 40 {
 41     int i,j,k;
 42     double mindis,sum=0;
 43     for(i=2;i<=c;i++)
 44     {
 45         vst[i]=0;
 46         dis[i]=map[1][i];
 47     }
 48     vst[1]=1;
 49     for(i=2;i<=c;i++)
 50     {
 51         k=1;
 52         mindis=INT_MAX;
 53         for(j=2;j<=c;j++)
 54             if(!vst[j]&&dis[j]<mindis)
 55             {
 56                 k=j;
 57                 mindis=dis[j];
 58             }
 59         if(mindis<INT_MAX)
 60         {
 61             sum+=mindis;
 62             vst[k]=1;
 63         }
 64         else
 65             return INT_MAX;
 66         for(j=2;j<=c;j++)
 67             if(map[k][j]<dis[j]&&!vst[j])
 68                 dis[j]=map[k][j];
 69     }
 70     return sum;
 71 }
 72 
 73 int main()
 74 {
 75     int i,j;
 76     double temp;
 77     while(~scanf("%d",&t))
 78     {
 79         while(t--)
 80         {
 81             scanf("%d",&c);
 82             for(i=1;i<=c;i++)
 83                 scanf("%lf%lf",&island[i].x,&island[i].y);
 84             for(i=1;i<=c;i++)
 85                 for(j=i;j<=c;j++)
 86                 {
 87                     temp=fun_dis(island[i].x,island[i].y,island[j].x,island[j].y);
 88                     if(temp>1000||temp<10)
 89                         map[i][j]=map[j][i]=INT_MAX;
 90                     else
 91                         map[i][j]=map[j][i]=temp;
 92                 }
 93             temp=prim();
 94             if(temp<INT_MAX)
 95                 printf("%.1lf\n",temp*100);
 96             else
 97                 printf("oh!\n");
 98         }
 99     }
100     return 0;
101 }