poj 2031Building a Space Station(几何判断+Kruskal最小生成树)

/*

  最小生成树 + 几何判断

  Kruskal      球心之间的距离 - 两个球的半径 < 0 则说明是覆盖的！此时的距离按照0计算 

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int f[105];

struct ball{

   double x, y, z, r;

};

struct connect{

   double dist;

   int a, b;

connect c[5005];

ball b[105];

bool cmp(connect a, connect b){

   return a.dist < b.dist;

}

int n;

int getFather(int x){

   return x==f[x] ? x : f[x]=getFather(f[x]); 

} 

int Union(int a, int b){

    int fa=getFather(a), fb=getFather(b);

    if(fa!=fb){

        f[fa]=fb;

        return 1;

    }

    return 0;

int main(){

   int i, j;

   while(scanf("%d", &n) && n){

      for(i=1; i<=n; ++i)

         scanf("%lf%lf%lf%lf", &b[i].x, &b[i].y, &b[i].z, &b[i].r);

      int cnt=0;

      for(i=1; i<n; ++i)

         for(j=i+1; j<=n; ++j){

             double d = sqrt((b[i].x-b[j].x)*(b[i].x-b[j].x) + (b[i].y-b[j].y)*(b[i].y-b[j].y) + (b[i].z-b[j].z)*(b[i].z-b[j].z))

                        - (b[i].r + b[j].r);

               c[cnt].dist= d<0 ? 0: d;

               c[cnt].a=i; 

               c[cnt++].b=j;

         }

       sort(c, c+cnt, cmp); 

       double minSum=0.0;

       for(i=1; i<=n; ++i)

          f[i]=i;

       for(i=0; i<cnt; ++i){

          if(Union(c[i].a, c[i].b))

             minSum+=c[i].dist;

       }

       printf("%.3lf\n", minSum);

   }

   return 0;

本文转自 小眼儿 博客园博客，原文链接：http://www.cnblogs.com/hujunzheng/p/3877502.html，如需转载请自行联系原作者