Freckles (最小生成树)

 1 #include<iostream>
 2 #include<cstring>
 3 #include<stdio.h>
 4 #include<queue>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<string>
 8 
 9 using namespace std;
10 
11 int Tree[101];
12 
13 int findRoot(int x)    // 查找节点x所在树的根节点 
14 {
15     if(Tree[x] == -1)
16         return x;
17     else    
18     {    // 路径优化 
19         int tmp = findRoot(Tree[x]);
20         Tree[x] = tmp;
21         return tmp;
22     }
23 }
24 
25 struct Edge     
26 {
27     double a, b;
28     double cost;
29 }edge[5010];
30 
31 bool cmp(Edge e1, Edge e2)
32 {
33     return e1.cost < e2.cost;
34 }
35 
36 struct Cursor    // 坐标结构 
37 {
38     double x, y;    // 点的坐标(x, y) 
39 }cur[101];
40 
41 int main()
42 {
43     int n;
44     while(scanf("%d", &n) != EOF)
45     {
46         for(int i = 1; i <= n; ++i)
47         {
48             Tree[i] = -1;    // 初始时，所有点都是孤立的集合 
49             // 此处不能写为scanf("%f %f", &(cur[i].x), &(cur[i].y)); 否则将产生输入错误 
50             scanf("%lf %lf", &(cur[i].x), &(cur[i].y));
51         }
52         
53         int k = 1;    // 抽象出的边的总数 
54         // 遍历所有的点对 
55         for(int i = 1; i <= n; ++i)        // 将坐标抽象为图中的顶点 
56         {
57             for(int j = i+1; j <= n; ++j)    // 连接两点的线段抽象成边 
58             {
59                 edge[k].a = i;    // 该边的两个顶点编号 
60                 edge[k].b = j;
61                 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));
62                 ++k;
63             }
64         }
65         sort(edge+1, edge+k, cmp);    // 对边按权值递增排序 
66             
67         // 最小生成树模板 
68         double ans = 0;
69         for(int i = 1; i < k; ++i)
70         {
71             int ra = findRoot(edge[i].a);
72             int rb = findRoot(edge[i].b);
73             if(ra != rb)
74             {
75                 Tree[ra] = rb;
76                 ans += edge[i].cost;
77             }
78         }
79         
80         printf("%.2lf
", ans);
81     }
82     
83     
84     
85     return 0;
86 }