题目大意：排座位，给出关系，B要在A后x位，给出许多的关系，求出错误的个数。
题解：加权并查集，注意关系不要弄混了。
|
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 |
#include <cstdio>int n, m, data, ans; int f[200010],r[200010]; int sf(int
x){ int
t; if(x==f[x])return
f[x]; t=f[x]; f[x]=sf(f[x]); r[x]+=r[t]; return
f[x]; } int
Union(int
x, int
y){ int
a, b; a=sf(x); b=sf(y); if(a==b){ if(r[y]!=r[x]+data) ans++; return
0; } else{ r[b]=r[x]+data-r[y]; f[b]=a; } return
0; } void
init(){ int
i; for(i=0;i<=n;i++){ f[i]=i; r[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,right); } printf("%d\n", ans); } return
0; } |
原文：http://www.cnblogs.com/forever97/p/3553208.html