Prim算法
#include <iostream>
#include <cstring>
#include <cmath>
int n;
double map[210][210],a[210];
int b[210];
void met(){
int i,t=1;
a[t]=0;
while(b[t]==0){
b[t]=1;
for(i=1;i<=n;i++)
if(b[i]==0&&a[i]>map[t][i])
a[i]=map[t][i];
double min=200000000;
for(i=1;i<=n;i++)if(b[i]==0&&min>a[i])min=a[i],t=i;
}
}
int main()
{
int i,j,k;
double f[210],g[210];
while(scanf("%d",&n)!=-1){
for(i=1;i<=n;i++)scanf("%lf%lf",&f[i],&g[i]);
memset(map,9,sizeof(map));
for(i=1;i<=110;i++)a[i]=200000000;
memset(b,0,sizeof(b));
double x,y,d;
for(i=1;i<=n;i++){
for(j=1;j<=i;j++){
x=f[i]-f[j];
y=g[i]-g[j];
d=sqrt(x*x+y*y);
map[i][j]=map[j][i]=d;
}
}met();
double sum=0;
for(i=1;i<=n;i++)sum+=a[i];
printf("%.2f
",sum);
}
return 0;
}