poj 2377 Bad Cowtractors

 1 #include<iostream>
 2 #include<cmath>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 #define maxn 1100
 7 int par[maxn];
 8 int n,m;
 9 int len;
10 int cnt;
11 struct node
12 {
13     int x;
14     int y;
15     int w;
16 };
17 node e[maxn * (maxn - 1) / 2];
18 int cmp(const node &a , const node &b)
19 {
20     return a.w > b.w;
21 };
22 void init()
23 {
24     for(int i = 1; i <= n+5; i++)
25         par[i] = i;
26     len = 0;
27     cnt = 0;
28 }
29 int Find(int x)
30 {
31     int k,j,r;
32     r = x;
33     while(par[r] != r)
34         r = par[r];
35     k = x;
36     while(k != r)
37     {
38         j = par[k];
39         par[k] = r;
40         k = j;
41     }
42     return r;
43 }
44 int Merge(int x,int y)
45 {
46     int a = Find(x);
47     int b = Find(y);
48     if(a != b)
49     {
50         par[a] = par[b];
51         return 1;
52     }
53     return 0;
54 }
55 
56 
57 void make()
58 {
59     for(int i = 0; i < m; i++)
60         scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);
61     sort(e,e+m,cmp);
62     for(int i = 0; i < m; i++)
63     {
64         if(Merge(e[i].x,e[i].y))
65         {
66             len += e[i].w;
67             cnt++;
68         }
69     }
70 }
71 int main()
72 {
73     freopen("input.txt","r",stdin);
74     while(scanf("%d%d",&n,&m) != EOF)
75     {
76         init();
77         make();
78         if(cnt == n-1) printf("%d
",len);
79         else printf("-1
");
80     }
81 
82     return 0;
83 }