tx1162.cpp

杭州电子科技大学在线系统ACM的1162题

#include <stdio.h>
#include <string.h>
#include <math.h>

double a[101][101];
int v[101];
int b[101];
double len;
int n;

void mintree()
{
int i,j;
double min;
int minnum;
int bnum=0;
b[0]=0;
v[0]=1;
bnum++;
  while(bnum!=n+1)
  {
    min=0.0;
    for(i=0;i<bnum;i++)
        for(j=0;j<n;j++)
          if(v[j]!=1)
            if(min==0.0||min>a[b[i]][j])
            {
            min=a[b[i]][j];
            minnum=j;
            }
    b[bnum]=minnum;
    v[minnum]=1;
    len+=min;
    bnum++; 
  }
}


int main()
{
int i,j;
double x[100],y[100],tmp;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
   scanf("%lf %lf",&x[i],&y[i]);
memset(a,0.0,sizeof(a));
memset(v,0,sizeof(v));
for(i=0;i<n;i++)
   for(j=i+1;j<n;j++)
{
tmp=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
a[i][j]=tmp;
a[j][i]=tmp;
}
len=0.0;
mintree();
printf("%.2f\n",len);
}
return 0;
}