題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=3038
題目和POJ那幾道題類似，都是并查集向量偏移來做，關(guān)系也比較好推導(dǎo)，p[x].r表示的是x與根節(jié)點(diǎn)的差，下面就是推導(dǎo)關(guān)系了
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstdlib>
4 #include <cstring>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 #define N 200010
9 struct data
10 {
11 int p, r;
12 }p[N];
13 int a[N];
14 int find(int x)
15 {
16 int temp;
17 if (p[x].p != x)
18 {
19 temp = p[x].p;
20 p[x].p = find(temp);
21 p[x].r = p[x].r + p[temp].r;
22 }
23 return p[x].p;
24 }
25 int main()
26 {
27 int n, m;
28 int x, y, s;
29 int r1, r2;
30 int ans;
31 while (scanf("%d%d", &n, &m) != EOF)
32 {
33 memset(a, -1, sizeof(a));
34 ans = 0;
35 for (int i = 1; i <= n; i++)
36 {
37 p[i].p = i;
38 p[i].r = 0;
39 }
40 for (int i = 0; i < m; i++)
41 {
42 scanf("%d%d%d", &x, &y, &s);
43 x--;
44 r1 = find(x); r2 = find(y);
45 if (r1 != r2)
46 {
47 p[r2].p = r1;
48 p[r2].r = p[x].r + s - p[y].r;
49 }
50 else
51 {
52 if (p[y].r - p[x].r != s) ans++;
53 }
54 }
55 printf("%d\n", ans);
56 }
57 return 0;
58