[ An Ac a Day ^_^ ][kuangbin带你飞]专题六 最小生成树 POJ 2031 Building a Space Station

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cmath>
  4 #include<cstring>
  5 #include<string>
  6 #define M(a,b) memset(a,b,sizeof(a))
  7 #define debug(x) cerr<<#x<<"=="<<(x)<<endl
  8 using namespace std;
  9 typedef long long ll;
 10 
 11 const int maxn=110;
 12 
 13 int f[maxn],tol,n;
 14 
 15 struct _edge
 16 {
 17     int u,v;
 18     double w;
 19 }edge[maxn*maxn*maxn];
 20 
 21 bool cmp(_edge a,_edge b)
 22 {
 23     return a.w<b.w;
 24 }
 25 
 26 struct point
 27 {
 28     int a;
 29     double x,y,z,r;
 30 } pt[maxn];
 31 
 32 void addedge(point a,point b)
 33 {
 34     edge[tol].u=a.a;
 35     edge[tol].v=b.a;
 36     double len=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z))-a.r-b.r;
 37     edge[tol].w=len<0?0:len;
 38     tol++;
 39 }
 40 
 41 //void addedge(int u,int v,int w)
 42 //{
 43 //    edge[tol].u=u;
 44 //    edge[tol].v=v;
 45 //    edge[tol].w=w;
 46 //    tol++;
 47 //}
 48 
 49 int _find(int x)
 50 {
 51     if(f[x]==-1) return x;
 52     else return f[x]=_find(f[x]);
 53 }
 54 
 55 double kruskal()
 56 {
 57     M(f,-1);
 58     sort(edge,edge+tol,cmp);
 59     int cnt=0;
 60     double ans=0,w;
 61     int u,v,f1,f2;
 62     for(int i=0; i<tol; i++)
 63     {
 64         u=edge[i].u;
 65         v=edge[i].v;
 66         w=edge[i].w;
 67         f1=_find(u);
 68         f2=_find(v);
 69         if(f1!=f2)
 70         {
 71             ans+=w;
 72             f[f1]=f2;
 73             cnt++;
 74         }
 75         if(cnt==n-1) break;
 76     }
 77     return ans;
 78 }
 79 
 80 int main()
 81 {
 82     while(scanf("%d",&n)!=EOF&&n)
 83     {
 84         tol=0;
 85         double x,y,z,r;
 86         for(int i=0; i<n; i++)
 87         {
 88             pt[i].a=i;
 89             scanf("%lf%lf%lf%lf",&pt[i].x,&pt[i].y,&pt[i].z,&pt[i].r);
 90             for(int j=0; j<i; j++)
 91             {
 92                 addedge(pt[j],pt[i]);
 93             }
 94         }
 95 
 96         printf("%.3f\n",kruskal()); //注意要用%f
 97     }
 98     return 0;
 99 }
100 /*
101 
102 3
103 10.000 10.000 50.000 10.000
104 40.000 10.000 50.000 10.000
105 40.000 40.000 50.000 10.000
106 2
107 30.000 30.000 30.000 20.000
108 40.000 40.000 40.000 20.000
109 5
110 5.729 15.143 3.996 25.837
111 6.013 14.372 4.818 10.671
112 80.115 63.292 84.477 15.120
113 64.095 80.924 70.029 14.881
114 39.472 85.116 71.369 5.553
115 0
116 
117 */