HDU-1233 还是畅通工程

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 
 6 int f[101];
 7 
 8 typedef struct e
 9 {
10     int a,b,w;
11 }eg;
12 eg e[5000];
13 
14 int cmp(eg x,eg y)
15 {
16     if(x.w<y.w)
17         return 1;
18     return 0;
19 }
20 
21 int find_set(int x)
22 {
23     if(x!=f[x])
24         f[x]=find_set(f[x]);///找到头
25 
26     return f[x];
27 }
28 
29 int main()
30 {
31     int n,m,z,x,y,i;
32 
33     while(scanf("%d",&n)&&n)
34     {
35         for(i=0;i<=n;i++)
36             f[i]=i;
37 
38         m=0;
39         z=n*(n-1)/2;
40 
41         for(i=0;i<z;i++)
42             scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
43         
44 
45         sort(e,e+z,cmp);
46 
47         for(i=0;i<z;i++)
48         { 
49             x=find_set(e[i].a);
50             y=find_set(e[i].b);
51 
52             if(x!=y)
53             {
54                 f[y]=x;
55                 m+=e[i].w;
56             }
57         }
58         printf("%d\n",m);
59     }
60     return 0;
61 }

 1 #include<cstdio>
 2 #include<algorithm>
 3 
 4 using namespace std;
 5 
 6 int p[110];
 7 
 8 struct data
 9 {
10     int x, y, money;
11 }v[5100];
12 
13 int cmp(data a, data b)
14 {
15     return a.money < b.money;
16 }
17 
18 int Find(int x)
19 {
20     if (x != p[x])
21         p[x] = Find(p[x]);
22 
23     return p[x];
24 }
25 
26 int main()
27 {
28     int n;
29 
30     while(scanf ("%d", &n), n != 0)
31     {
32 
33         int i, z = n*(n-1)/2;
34 
35         for (i = 1; i <= n; i++)
36             p[i] = i;
37 
38         for (i = 0; i < z; i++)
39             scanf ("%d %d %d", &v[i].x, &v[i].y, &v[i].money);
40 
41         sort(v, v+z, cmp);
42 
43         int a, b, num = 0;
44 
45         for (i = 0; i < z; i++)
46         {
47             a = Find(v[i].x);
48             b = Find(v[i].y);
49 
50             if (a != b)
51             {
52                 p[b] = a;
53                 num += v[i].money;
54             }
55         }
56 
57         printf("%d\n", num);
58 
59     }
60     return 0;
61 }