题解：用加权并查集，将小的节点作为父节点，每一次压缩路径时传递和的信息，如果已有信息存在，判断是否是正确的即可：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 |
#include <cstdio> int n, m, data, ans; int f[200010],sum[200010]; int sf(int
x){ int
t; if(x==f[x])return
f[x]; t=f[x]; f[x]=sf(f[x]); sum[x]+=sum[t]; return
f[x]; } int
Union(int
x, int
y){ int
a, b; a=sf(x); b=sf(y); if(a==b){ if(sum[y]!=sum[x]+data) ans++; return
0; } if(a>b){ sum[a]=sum[y]-sum[x]-data; f[a]=b; } else{ sum[b]=sum[x]+data-sum[y]; f[b]=a; } return
0; } void
init(){ int
i; for(i=0;i<=n;i++){ f[i]=i; sum[i]=0; } } int
main(){ int
i, j, left, right; while(scanf("%d%d", &n, &m) != EOF){ ans = 0; init(); for(i = 0 ; i < m ; i++){ scanf("%d%d%d",&left,&right,&data); Union(left-1,right); } printf("%d\n", ans); } return
0; } |
HDU 3038 How Many Answers Are Wrong
原文：http://www.cnblogs.com/forever97/p/3553168.html