poj 2560 || 杭电1162

杭电上为多实例测试，poj上为单实例，在此，列出poj代码
View Code
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #define M 200000000
 5 #define N 110
 6 double map[N][N],a[N],b[N];
 7 int n;
 8 void met()//简单的最小生成树算法
 9 {
10     int i,k;
11     double min;
12     k=1;
13     a[k]=0;
14     while(b[k]==0)
15     {
16         b[k]=1;
17         for(i=1;i<=n;i++)
18             if(b[i]==0&&a[i]>map[k][i])
19                 a[i]=map[k][i];
20             min=200000000;
21             for(i=1;i<=n;i++)
22                 if(b[i]==0&&a[i]<min)
23                 {
24                     min=a[i];

25                     k=i;
26                 }
27     }
28     
29 }
30 
31 
32 int main()
33 {
34     int i,j;
35     scanf("%d",&n);
36     
37     double x,y,dis,c[110],d[110];
38     for(i=1;i<=n;i++)
39     {
40         a[i]=M;
41         for(j=1;j<=n;j++)
42             map[i][j]=M;
43     }
44     memset(b,0,sizeof(b));
45     for(i=1;i<=n;i++)
46     {
47         scanf("%lf%lf",&c[i],&d[i]);
48     }
49     for(i=1;i<=n;i++)
50         for(j=1;j<=i;j++)
51         {
52             x=c[i]-c[j];
53             y=d[i]-d[j];
54             dis=sqrt(x*x+y*y);//求两点之间距离
55             map[i][j]=map[j][i]=dis;
56         }
57         met();
58         double sum=0;
59         for(i=1;i<=n;i++)
60             sum+=a[i];
61         printf("%.2f\n",sum);
62         return 0;
63 }