POJ2031 Building a Space Station

題目傳送門：http://poj.org/problem?id=2031

題意：就是給出空間中點的坐标和半徑，讓我們求怎麼連接配接花費最少，其中假如兩個圓是相交的話認為這兩個球是連通的。

分析：先求出所有的點的距離之後再克魯斯卡爾就好了，注意輸出的時候使用%f假如你用的是G++送出的話。

代碼

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
    double a,b,c,d;
}a[105];
struct link{
    int a,b;
    double c;
}b[1000000];
int father[105];
double  cnt;
void init(){
    for(int i=0;i<105;i++) father[i]=i;
}
int find_father(int x){
    return father[x]==x?x:father[x]=find_father(father[x]);
}
void union_tree(int x,int y,double z){
    x=find_father(x);
    y=find_father(y);
    if(x==y) return;
    father[x]=y;
    cnt+=z;
}
int cmp(link a,link b){
    return a.c<b.c;
}
int main(void){
    int n,j,i,k;
    double m;
    while(scanf("%d",&n)&&n){
        init();
        for(i=0;i<n;i++)
            scanf("%lf %lf %lf %lf",&a[i].a,&a[i].b,&a[i].c,&a[i].d);
        for(i=0,k=0;i<n;i++)
            for(j=i+1;j<n;j++){
                m=sqrt((a[i].a-a[j].a)*(a[i].a-a[j].a)+(a[i].b-a[j].b)*(a[i].b-a[j].b)+(a[i].c-a[j].c)*(a[i].c-a[j].c));
                b[k].a=i;b[k].b=j;b[k].c=m-a[i].d-a[j].d>0?m-a[i].d-a[j].d:0;
                k++;
            }
        sort(b,b+k,cmp);
        for(i=0,cnt=0;i<k;i++)
            union_tree(b[i].a,b[i].b,b[i].c);
        printf("%.3f\n",cnt);
    }
}