hdu1162Eddy's picture

http://acm.hdu.edu.cn/showproblem.php?pid=1162
最小生成树
 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<math.h>
 4 #include<string.h>
 5 #include<stdlib.h>
 6 using namespace std;
 7 const int N=5005;
 8 struct stu{
 9     int u;
10     int v;
11     double w;
12 }p[N];
13 
14 struct ln{
15     double x;
16     double y;
17 }q[N];
18 int father[N];
19 int n,m,k;
20 
21 int cmp(const void *a,const void *b)
22 {
23     return (*(struct stu*)a).w > (*(struct stu*)b).w ?1:-1;
24 }
25 int find(int x)
26 {
27     if(father[x]!=x)
28     father[x]=find(father[x]);
29     return father[x];
30 }
31 int make(int a,int b)
32 {
33     int h=0;
34     int f1=find(a);
35     int f2=find(b);
36     if(f1>f2)
37     {
38         father[f1]=f2;
39         h=1;
40     }
41     else if(f1<f2)
42     {
43         father[f2]=f1;
44         h=1;
45     }
46     return h;
47 }
48 double kruskal()
49 {
50     int cnt=0;
51     double s=0;
52     for(int i=0;i<k;i++)
53     {
54         if(make(p[i].u,p[i].v))
55         {
56             s+=p[i].w;
57             cnt++;
58         }
59         if(cnt==n-1)
60         return s;
61     }
62     return s;
63 }
64 void zuhe()
65 {
66     k=0;
67     for(int i=0;i<n;i++)
68     {
69         for(int j=i+1;j<n;j++)
70         {
71             p[k].u=i+1;
72             p[k].v=j+1;
73             p[k++].w=sqrt((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y));
74         }
75     }
76 }
77 
78 int main()
79 {
80     //freopen("in.txt","r",stdin);
81     while(~scanf("%d",&n))
82     {
83         for(int i=1;i<=n;i++)
84         father[i]=i;
85         for(int i=0;i<n;i++)
86         {
87             scanf("%lf%lf",&q[i].x,&q[i].y);
88         }
89         zuhe();
90         qsort(p,k,sizeof(struct stu),cmp);
91 //        for(int i=0;i<k;i++)
92 //        {
93 //            printf("%d %d %lf
",p[i].u,p[i].v,p[i].w);
94 //        }
95         printf("%.2lf
",kruskal());
96     }
97     return 0;
98 }