#include <iostream>
#include<stdio.h>
#include<math.h>
#include<memory>
#include<string.h>
using namespace std;
int N;
double x[105],y[105],z[105],r[105];
double dis[105];
int visited[105];
double ans;
double getdis(int i,int j)
{
    double t = 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]));
    if(t > r[i] + r[j])return t - r[i] - r[j];
    else return 0;
}
void prim()
{
    ans = 0.0;
    for(int i = 0 ;i < N;i ++)
    {
        dis[i] = getdis(0,i);
    }
    memset(visited,0,sizeof(visited));
    visited[0] = 1;
    for(int i = 1 ; i < N ; i ++)
    {
        int  u = 0;
        double min = 10000.0;
        for(int j = 0 ; j < N ;j ++)
        {
            if(visited[j] == 0 && min > dis[j])
            {
                min = dis[j];
                u = j;
            }
        }
        visited[u] = 1;
        ans = ans + min;
        for(int j = 0 ; j < N ; j ++)
        {
            if(visited[j] == 0)
            {
                double t = getdis(u,j);
                if(dis[j] > t)
                    dis[j] = t;
            }
        }

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

}
int main()
{
    freopen("datain.in","r",stdin);
    while(scanf("%d",&N) && N)
    {
        for(int i = 0;i < N;i ++)
        {
            scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
        }
        prim();
    }
    return 0;
}

• Re:我的也是 高手看看！ (1742) qiuzhenguang 2010-04-24 12:11:36