uva 10034【Freckles】

Krustral是也。。。
View Code
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cmath>
 5 
 6 struct segment 
 7 {
 8     int u,v;
 9     double w;
10 }s[10000];
11 
12 struct point
13 {
14     double x,y;
15 }p[110];
16 
17 int f[105];
18 int n;
19 int sum;
20 double len;
21 
22 bool cmp(const segment &a,const segment &b)
23 {
24     if(a.w == b.w)
25         return a.u < b.u;
26     return a.w < b.w;
27 }
28 
29 double dis(point a,point b)
30 {
31     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y)*(a.y - b.y));
32 }
33 
34 int find(int x)
35 {
36     if(x == f[x])
37         return x;
38     f[x] = find(f[x]);
39 
40     return f[x];
41 }
42 
43 void krustral()
44 {
45     len = 0;
46     for(int i = 0;i < sum;i ++)
47     {
48         int fa = find(s[i].u);
49         int fb = find(s[i].v);
50         if(fa != fb)
51         {
52             f[fa] = fb;
53             len += s[i].w;
54         }
55     }
56     printf("%.2lf\n",len);
57 }
58 int main()
59 {
60     int cas;
61     scanf("%d",&cas);
62     while(cas --)
63     {
64         scanf("%d",&n);
65         sum = 0;
66         for(int i = 0;i < n;i ++)
67         {
68             scanf("%lf%lf",&p[i].x,&p[i].y);
69             for(int j = 0;j < i;j ++)
70             {
71                 s[sum].u = i;
72                 s[sum].v = j;
73                 s[sum ++].w = dis(p[i],p[j]);
74             }
75         }
76         std::sort(s,s + sum,cmp);
77 
78         for(int i = 0;i <= n;i ++)
79         {
80             f[i] = i;
81         }
82 
83         krustral();
84         if(cas)
85             printf("\n");
86     }
87 
88     return 0;
89 }