Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:我的也是 高手看看！

Posted by qiuzhenguang at 2010-04-24 12:11:36 on Problem 2031
In Reply To:我的也是 高手看看！ Posted by:0712105003 at 2010-04-11 18:51:05

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "math.h"
#define MAXN 105
#define MAXF (1.0e15)
int n,vis[MAXN];
double x[MAXN],y[MAXN],z[MAXN],r[MAXN],d[MAXN][MAXN];

int BuildGraph()
{
for (int i=0;i<n;i++)
{
scanf("%lf%lf%lf%lf",x+i,y+i,z+i,r+i);
}
for (int i=0;i<n;i++)
for (int j=i;j<n;j++)
{
if (i==j)
{
d[i][j]=0.0;
}
else
{
double dis=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]) )-r[i]-r[j];
d[i][j]= dis>0.0?dis:0.0;
d[j][i]=d[i][j];
}
}
return 0;
}

double Prim()
{
double sum=0.0,l[MAXN],min;
int u,i,j;
memset(vis,0,sizeof(vis));
u=0;vis[u]=1;
for (i=0;i<n;i++)
{
l[i]=d[u][i];
}
for (i=0;i<n;i++)
{
min=MAXF;
for (j=0;j<n;j++)
{
if (!vis[j] && l[j]<min)
{
min = l[j];
u=j;
}
}
vis[u]=1;
for (j=0;j<n;j++)
{
if   (!vis[j] && l[j]>d[u][j])
{
l[j]=d[u][j];
}
}
}
for (i=0;i<n;i++)
sum+=l[i];
return sum;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&n);
while (n!=0)
{
BuildGraph();
printf("%.3lf\n",Prim());
scanf("%d",&n);
}

return 0;
}

Followed by: