2 2 10 10 20 20 3 1 1 2 2 1000 1000
1414.2 oh!
#include <cstdio>
#include<cstring>
#include <math.h>
#define MAX 0xfffffff
double map[110][110],dis[110],len,min,sum;
int T,n,mini,mark[110];
void prim()
{
int i,j;
sum=0;
memset(mark,0,440);
mark[1]=1;
for(i=1;i<=n;++i)
dis[i]=map[1][i];
for(i=1;i<n;++i)
{
min=MAX;
mini=0;
for(j=2;j<=n;++j)
if(min>dis[j]&&!mark[j])
min=dis[mini=j];
if(min==MAX)
{
printf("oh!\n");return ;
}
sum+=min;
mark[mini]=1;
for(j=1;j<=n;++j)
if(!mark[j]&&dis[j]>map[mini][j])
dis[j]=map[mini][j];
}
printf("%.1lf\n",sum*100);
}
int main()
{
int p[110][2],i,j;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
map[i][j]=MAX;
for(i=1;i<=n;++i)
scanf("%d%d",&p[i][0],&p[i][1]);
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
len=sqrt(double((p[i][0]-p[j][0])*(p[i][0]-p[j][0])+(p[i][1]-p[j][1])*(p[i][1]-p[j][1])));
if(len>=10&&len<=1000)
map[i][j]=map[j][i]=len;
}
prim();
}
return 0;
}原文:http://blog.csdn.net/hpuhjl/article/details/38517481