HDU 3047 Zjnu Stadium（带权并查集）

http://acm.hdu.edu.cn/showproblem.php?pid=3047

题意：

给出n个座位，有m次询问，每次a，b，d表示b要在a右边d个位置处，问有几个询问是错误的。

思路：

基础带权并查集。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 const int maxn = 50000+5;
 5 
 6 int n,m;
 7 int p[maxn],r[maxn];
 8 
 9 int finds(int x)
10 {
11     if(p[x]==x)  return x;
12     int tmp = p[x];
13     p[x] = finds(p[x]);
14     r[x] = r[x] + r[tmp];
15     return p[x];
16 }
17 
18 void unions(int a, int b, int x, int y, int d)
19 {
20     p[x] = y;
21     r[x] = d+r[b]-r[a];
22 }
23 
24 int main()
25 {
26     //freopen("in.txt","r",stdin);
27     while(~scanf("%d%d",&n,&m))
28     {
29         int ans = 0;
30         for(int i=0;i<=n;i++)   {p[i] = i;r[i] = 0;}
31         while(m--)
32         {
33             int a,b,d;
34             scanf("%d%d%d",&a,&b,&d);
35             int x = finds(a);
36             int y = finds(b);
37             if(x==y)
38             {
39                 if(r[a]-r[b]!=d)  ans++;
40             }
41             else
42             {
43                 unions(a,b,x,y,d);
44             }
45         }
46         printf("%d
",ans);
47     }
48     return 0;
49 }