zoj1718 Building a Space Station poj2031

  1 #include <iostream>
  2 #include<stdio.h>
  3 #include<string.h>
  4 #include<math.h>
  5 #include<algorithm>
  6 #define MAXN 101
  7 #define MAXM 10000
  8 using namespace std;
  9 struct edge
 10 {
 11     int u,v;
 12     double w;
 13 }edges[MAXM];
 14 int parent[MAXN];
 15 int N,M;
 16 double X[MAXN],Y[MAXN],Z[MAXN],R[MAXN];
 17 int i,j;
 18 double sumweight;
 19 void UFset()
 20 {
 21     for(i=0; i<N; i++)
 22     {
 23         parent[i]=-1;
 24     }
 25 }
 26 int Find(int x)
 27 {
 28     int s;
 29     for(s=x; parent[s]>0;s=parent[s]);
 30     while(s!=x)
 31     {
 32         int tmp=parent[x];
 33         parent[x]=s;
 34         x=tmp;
 35     }
 36     return s;
 37 }
 38 void Union(int R1,int R2)
 39 {
 40     int r1=Find(R1);
 41     int r2=Find(R2);
 42     int tmp=parent[r1]+parent[r2];
 43     if(parent[r1]<parent[r2])
 44     {
 45         parent[r2]=r1;
 46         parent[r1]=tmp;
 47     }
 48     else
 49     {
 50         parent[r1]=r2;
 51         parent[r2]=tmp;
 52     }
 53 }
 54 int cmp(const void *a,const void *b)
 55 {
 56     edge aa=*(const edge *)a;
 57     edge bb=*(const edge *)b;
 58     if(aa.w>bb.w)
 59     return 1;
 60     else return -1;
 61 }
 62 void Kruskal()
 63 {
 64     int num=0;
 65     int u,v;
 66     UFset();
 67 
 68     for(i=0;i<M;i++)
 69     {
 70          u=edges[i].u;
 71          v=edges[i].v;
 72          if(Find(u)!= Find(v))
 73          {
 74              sumweight+=edges[i].w;
 75              num++;
 76 
 77              Union(u,v);
 78 
 79          }
 80          if(num==N-1)break;
 81 
 82     }
 83 }
 84 int main()
 85 {
 86     double d;
 87     while(scanf("%d",&N)!=EOF&&N!=0)
 88     {
 89         for(i=0; i<N; i++)
 90         {
 91             scanf("%lf%lf%lf%lf",&X[i],&Y[i],&Z[i],&R[i]);
 92         }
 93 
 94         int mi=0;
 95         for(i=0; i<N; i++)
 96         {
 97             for(j=i+1; j<N; j++)
 98             {
 99                 d=sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])+(Z[i]-Z[j])*(Z[i]-Z[j]));
100                 edges[mi].u=i;
101                 edges[mi].v=j;
102                 if(d-R[i]-R[j]>0)
103                 {
104                     edges[mi].w=d-R[i]-R[j];
105                 }
106                 else {edges[mi].w=0;}
107                 mi++;
108             }
109         }
110 
111         M=mi;
112         qsort(edges,M,sizeof(edges[0]),cmp);
113         sumweight=0.0;
114         Kruskal();
115         printf("%.3lf
",sumweight);
116     }
117     return 0;
118 }
View Code