hdu 3038 How Many Answers Are Wrong (带权并查集)

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 200000+10;
 7 int bin[maxn], dist[maxn], ans;
 8 
 9 int find(int x)
10 {
11     if(x==bin[x]) return x;
12     int tmp = bin[x];
13     bin[x] = find(bin[x]);
14     dist[x] += dist[tmp];
15     return bin[x];
16 }
17 void merge(int x, int y, int s)
18 {
19     int fx = find(x);
20     int fy = find(y);
21     if(fx == fy)
22     {
23         if(dist[y] != dist[x] + s)
24             ans++;
25     }
26     else
27     {
28         bin[fy] = fx;
29         dist[fy] = dist[x] - dist[y] + s;
30     }
31 }
32 int main()
33 {
34     int n, m, i, a, b, s;
35     while(~scanf("%d%d", &n, &m))
36     {
37         ans = 0;
38         for(i = 1; i <= n; i++)
39         {
40             bin[i] = i;
41             dist[i] = 0;
42         }
43         while(m--)
44         {
45             scanf("%d%d%d", &a, &b, &s);
46             a--;  //注意
47             merge(a, b, s);
48         }
49         printf("%d\n", ans);
50     }
51     return 0;
52 }