poj 2031 Kruskal

[cpp] 
//計算幾何+最小生成樹  
//注意精度  
//若兩單元園心距離小與半徑之和，則距離為0  
//反之，為距離-半徑之和  
 
#include <iostream>  
#include <algorithm>  
#include <cstdio>  
#include <cmath>  
using namespace std; 
 
const int MAXN = 101; 
const int MAXM = 500000; 
int n; 
int M; 
double cost; 
double eps = 0.0000001; 
 
struct edge 
{ 
    int u; 
    int v; 
    double w; 
}edges[MAXM]; 
 
struct unit 
{ 
    double x; 
    double y; 
    double z; 
    double r; 
}units[MAXN]; 
 
int cmp(const void *a,const void *b) 
{ 
    edge aa = *(const edge *)a; 
    edge bb = *(const edge *)b; 
    return aa.w - bb.w; 
} 
 
int Father[MAXN]; 
int Rank[MAXN]; 
 
void Make_Set() 
{ 
    for(int i = 0; i < MAXN; i++) 
    { 
        Father[i] = i; 
        Rank[i] = 1; 
    } 
} 
 
int Find(int x) 
{ 
    while(x != Father[x]) 
        x = Father[x]; 
    return x; 
} 
 
void Union(int x,int y) 
{ 
    x = Find(x); 
    y = Find(y); 
    if(x == y) 
        return; 
    if(Rank[x] > Rank[y]) 
    { 
        Father[y] = x; 
        Rank[x] += Rank[y]; 
    } 
    else 
    { 
        Father[x] = y; 
        Rank[y] += Rank[x]; 
    } 
} 
 
 
 
double distance(double x1,double y1,double z1,double x2,double y2,double z2) 
{ 
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1)); 
} 
 
 
void Kruskal() 
{ 
    int u,v; 
    Make_Set(); 
    for(int i = 0; i < M; i++) 
    { 
        u = Find(edges[i].u); 
        v = Find(edges[i].v); 
        if(u != v) 
        { 
            cost += edges[i].w; 
            Union(u,v); 
        } 
    } 
} 
 
int main() 
{ 
    while(cin>>n) 
    { 
        if(n == 0) 
            break; 
        for(int i = 0; i < n; i++) 
        { 
            cin>>units[i].x>>units[i].y>>units[i].z>>units[i].r; 
        } 
        M = 0; 
        cost = 0; 
        for(int i = 0; i < n-1; i++) 
        { 
            for(int j = 1; j < n; j++ ) 
            { 
                double dis = distance(units[i].x,units[i].y,units[i].z,units[j].x,units[j].y,units[j].z); 
                edges[M].u = i; 
                edges[M].v = j; 
                if((dis - (units[i].r + units[j].r)) < eps) 
                { 
                    edges[M].w = 0; 
                } 
                else 
                { 
                    edges[M].w = dis - (units[i].r + units[j].r);     
                    //cout<<dis<<endl;  
 
                } 
                M++; 
            } 
        } 
        qsort(edges,M,sizeof(edges[0]),cmp); 
        Kruskal(); 
        printf("%.3f\n",cost); 
    } 
    return 0; 
}