1 #include <iostream> 2 #include <cmath> 3 #include <cstdio> 4 #include <cstring> 5 #define INF 999999 6 #define MAXN 101 7 using namespace std; 8  9 double weight[MAXN][MAXN];10 11 struct Point{12     double x_;13     double y_;14 }FreckMap[MAXN];15 16 void init(int FreckNum);17 double dist(Point last,Point now);18 void prim(int Num);19 20 int main()21 {22     #ifndef ONLINE_JUDGE23         freopen("D:\\acm.txt","r",stdin);24     #endif // ONLINE_JUDGE25     int caseNum,FreckNum;26     scanf("%d",&caseNum);27     while(caseNum--){28         scanf("%d",&FreckNum);29         for(int i = 0;i < FreckNum;i++)30             scanf("%lf%lf",&FreckMap[i].x_,&FreckMap[i].y_);31         init(FreckNum);32         prim(FreckNum);33         if(caseNum)34             printf("\n");35     }36     return 0;37 }38 39 void init(int FreckNum){40     for(int i = 0;i < FreckNum;i++){41         for(int j = 0;j < FreckNum;j++){42             if(i == j)continue;43             weight[i][j] = dist(FreckMap[i],FreckMap[j]);44         }45     }46 }47 double dist(Point last,Point now){48     double dis;//暂时先不开方49     return dis = (last.x_ - now.x_)*(last.x_ - now.x_) + (last.y_ - now.y_)*(last.y_ - now.y_) ;50 }51 void prim(int Num){52     double lowcost[MAXN];53     int joinPoint,closest[MAXN];54     double min,pathDis = 0.0;55     for(int i = 0;i < Num;i++){         //给lowcost[]和closets[]置初值56         lowcost[i] = weight[0][i];57         closest[i] = 0;58     }59     for(int i = 1;i < Num;i++){         //找出（n-1）个顶点60         min = INF;61         for(int j = 0;j < Num;j++){     //在（V——U）中找出离U最近的顶点joinPoint62             if(lowcost[j] != 0&&lowcost[j] < min){63                 min = lowcost[j];64                 joinPoint = j;          //joinPoint记录最近顶点的编号65             }66         }67         pathDis += sqrt(min);           //生成树的总长68         lowcost[joinPoint] = 0;         //标记joinpoint已经加入U69         for(int j = 0;j < Num;j++){     //修改数组lowcost和closest70             if(weight[joinPoint][j] != 0&&weight[joinPoint][j] < lowcost[j]){71                 lowcost[j] = weight[joinPoint][j];72                 closest[j] = joinPoint;73             }74         }75     }76     printf("%.2lf\n",pathDis);77 }