带权并查集 - How Many Answers Are Wrong

 1 #include <iostream>
 2 using namespace std;
 3 int n, m;
 4 int pre[200005];
 5 int f[200005];   // 到根节点的距离
 6 int ans = 0;
 7 
 8 void init()
 9 {
10     for (int i = 0; i <= n; i++) {
11         pre[i] = i;
12         f[i] = 0;
13     }
14 }
15 
16 int Find(int x)
17 {
18     if (x == pre[x])
19         return x;
20     int y = pre[x];
21     pre[x] = Find(pre[x]);
22     f[x] += f[y];
23     return pre[x];
24 }
25 
26 void Union(int x, int y, int s)
27 {
28     int fx = Find(x);
29     int fy = Find(y);
30     if (fx != fy) {
31         pre[fx] = fy;
32         f[fx] = f[y] + s - f[x];
33     }
34     else if (f[x] - s != f[y])
35             ans++;
36 }
37 
38 int main()
39 {
40     ios::sync_with_stdio(false);
41     cin.tie(0);
42     while (cin >> n >> m) {
43         ans = 0;
44         init();
45         for (int i = 0; i < m; i++) {
46             int a, b, s;
47             cin >> a >> b >> s;
48             Union(a - 1, b, s);
49         }
50         cout << ans << endl;
51     }
52     return 0;
53 }