hdu 3047 Zjnu Stadium 带权并查集

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 
 5 const int maxn = 50005;
 6 int f[maxn], rank[maxn];
 7 int n, m;
 8 
 9 void init(){
10     for (int i = 0; i <= n; ++i){
11         f[i] = i;
12         rank[i] = 0;
13     }
14     return;
15 }
16 
17 int find(int x){
18     if (x == f[x])
19         return f[x];
20     int t = f[x];
21     f[x] = find(f[x]);
22     rank[x] += rank[t];        //把父辈的加起来
23     return f[x];
24 }
25 
26 bool Union(int x, int y, int m){
27     int a = find(x);
28     int b = find(y);
29     if (a == b){
30         if (rank[x] + m != rank[y])
31             return false;
32         return true;
33     }
34     f[b] = a;
35     rank[b] = rank[x] + m - rank[y];
36     return true;
37 }
38 
39 int main(){
40     int a, b, x;
41     while (~scanf("%d%d", &n, &m)){
42         init();
43         int cnt = 0;
44         for (int i = 0; i<m; ++i){
45             scanf("%d%d%d", &a, &b, &x);
46             if (!Union(a, b, x)){
47                 cnt++;
48             }
49         }
50         printf("%d
", cnt);
51     }
52     return 0;
53 }