Freckles (最小生成树)

 #include<iostream>

 #include<cstring>

 #include<stdio.h>

 #include<queue>

 #include<cmath>

 #include<algorithm>

 #include<string>

 using namespace std;

 int Tree[];

 int findRoot(int x)    // 查找节点x所在树的根节点

 {

     if(Tree[x] == -)

         return x;

     else

     {    // 路径优化

         int tmp = findRoot(Tree[x]);

         Tree[x] = tmp;

         return tmp;

     }

 }

 struct Edge

 {

     double a, b;

     double cost;

 }edge[];

 bool cmp(Edge e1, Edge e2)

 {

     return e1.cost < e2.cost;

 }

 struct Cursor    // 坐标结构

 {

     double x, y;    // 点的坐标(x, y)

 }cur[];

 int main()

 {

     int n;

     while(scanf("%d", &n) != EOF)

     {

         for(int i = ; i <= n; ++i)

         {

             Tree[i] = -;    // 初始时，所有点都是孤立的集合

             // 此处不能写为scanf("%f %f", &(cur[i].x), &(cur[i].y)); 否则将产生输入错误

             scanf("%lf %lf", &(cur[i].x), &(cur[i].y));

         }

         int k = ;    // 抽象出的边的总数

         // 遍历所有的点对

         for(int i = ; i <= n; ++i)        // 将坐标抽象为图中的顶点

         {

             for(int j = i+; j <= n; ++j)    // 连接两点的线段抽象成边

             {

                 edge[k].a = i;    // 该边的两个顶点编号

                 edge[k].b = j;

                 edge[k].cost = sqrt((cur[j].x-cur[i].x)*(cur[j].x-cur[i].x)+(cur[j].y-cur[i].y)*(cur[j].y-cur[i].y));

                 ++k;

             }

         }

         sort(edge+, edge+k, cmp);    // 对边按权值递增排序

         // 最小生成树模板

         double ans = ;

         for(int i = ; i < k; ++i)

         {

             int ra = findRoot(edge[i].a);

             int rb = findRoot(edge[i].b);

             if(ra != rb)

             {

                 Tree[ra] = rb;

                 ans += edge[i].cost;

             }

         }

         printf("%.2lf\n", ans);

     }

     return ;

 }