HDU1875prim算法求最小生成树

畅通工程再续

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

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

Sample Output

1414.2
oh!

Author

8600

Source

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

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <vector>
  8 #include <stack>
  9 #include <queue>
 10 #include <cassert>
 11 #include <set>
 12 #include <sstream>
 13 #include <map>
 14 using namespace std ;
 15 #ifdef DeBUG
 16 #define bug assert
 17 #else
 18 #define bug //
 19 #endif
 20 #define zero {0}
 21 #define INF 0x7fffffff
 22 #define eps 1e-6
 23 struct seg
 24 {
 25     int a;
 26     int b;
 27     double dis;
 28 };
 29 seg v[7000];
 30 int father[101];
 31 double sum;
 32 double Dis(double x1,double y1,double x2,double y2)
 33 {
 34     return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
 35 }
 36 int cmp(const void *a,const void *b)
 37 {
 38     seg c=*(seg *)a;
 39     seg d=*(seg *)b;
 40     return c.dis>d.dis? 1:-1;//这里很重要啊有木有，精度丢失有木有！ 
 41 }
 42 int findx(int x)
 43 {
 44     if(father[x]!=x)
 45         father[x]=findx(father[x]);
 46     return father[x];
 47 }
 48 void merge(int x,int y,int t)
 49 {
 50     int fx,fy;
 51     fx=findx(x);
 52     fy=findx(y);
 53     if(fx!=fy)
 54     {
 55         father[fx]=fy;
 56         sum+=v[t].dis;
 57     }
 58 }
 59 int main()
 60 {
 61 #ifdef DeBUG
 62     freopen("C:\Users\Sky\Desktop\1.in","r",stdin);
 63 //    freopen("C:\Users\Sky\Desktop\打表.txt","w",stdout);//PLEASE DELETE IT!!!!!!!!!!!!!!!!!!!!!!!!
 64 #endif
 65     int T;
 66     scanf("%d",&T);
 67     while(T--)
 68     {
 69     //    memset(father,0,sizeof(father));
 70     //    memset(v,0,sizeof(v));
 71         int n;
 72         int a[200][2]=zero;//记录坐标 
 73         double s;//临时记录点间距离 
 74         sum=0;//答案 
 75         scanf("%d",&n);//n个点啊 
 76         int i,j,k;
 77         for(i=0; i<n; i++)//初始化啊 
 78             father[i]=i;
 79         for(i=0; i<n; i++)
 80             scanf("%d %d",&a[i][0],&a[i][1]);
 81         k=0;//下标从0开始啊 
 82         for(i=0; i<n; i++)
 83             for(j=i+1; j<n; j++)
 84             {
 85                 s=Dis(a[i][0],a[i][1],a[j][0],a[j][1]);
 86                 if(s>=10&&s<=1000)//满足条件构成边 啊 
 87                 {
 88                     v[k].a=i;//一个端点啊 
 89                     v[k].b=j;//两个端点啊 
 90                     v[k].dis=s;
 91                     k++;
 92                     //s=0;
 93                 }
 94             }
 95         qsort(v,k,sizeof(v[0]),cmp);//prim 排序啊 
 96         sum=0;//又TM初始化一遍啊 ⊙﹏⊙b 
 97         for(i=0; i<k; i++)
 98             merge(v[i].a,v[i].b,i);//合并操作啊，需要加第i个边的距离就传个i啊 
 99         int cnt=0;
100         for(i=0; i<n; i++)
101             if(father[i]==i)//求连通图数啊 
102                 cnt++;
103         if(cnt==1)//图连通啊 
104             printf("%.1lf
",100*sum);
105         else
106             printf("oh!
");
107        //     for(i=1;i<=n;i++)
108          //   printf("%d %d %lf
",v[i].a,v[i].b,v[i].dis);
109     }
110     return 0;
111 }

View Code