#include <cstdio>
#include <cstring>
#include <cmath>

#define I_NF 1000000

const int M =1005;

int map[666][666];
int mark[666];
double d [M];


double prim(int K)
{
     int i,j,n,l;
     for(i=1;i<=K;i++)
      d[i]=map[1][i];
      mark[1]=1;
      double s=0; //权值
      for(i=1;i<=K;i++)
      {
           double min=I_NF+5;
           int Record=-5;
           for(j=1;j<=K;j++)
           {
                if(d[j]<min&&mark[j]==0)
                {
                     min=d[j];
                     Record=j;
                }
           }

           if(Record<0)
            break;
            s+=min;
           mark[Record]=1;
           for(j=1;j<=K;j++)
           {
                if(!mark[j]&&map[Record][j]<d[j])
                {
                     d[j]=map[Record][j];
                }
           }
      }
      return s;

}
int main()
{
    int n;
    double x[200],y[200],z[200],r[200];
    while(scanf("%d",&n)&&n!=0){
            int i,j,k;
            for(i=1;i<=n;i++){
                scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
            }
            for(i=1;i<=n;i++){
                    for(j=1;j<=n;j++){
                map[i][j] = (double) (sqrt( pow(x[i]-x[j],2)+pow(y[i]-y[j],2)+pow(z[i]-z[j],2)) - r[i] -r[j]);
                if(map[i][j]<0)
                    map[i][j] = (double)0;
                    }
            }





    printf("%.3lf\n",prim(n));
    }
    return 0;
}

• Re:为什么会WA (1651) lyz963254 2014-12-11 22:55:03
• Re:为什么会WA (1681) lyz963254 2014-12-11 22:55:45