HDU 3047 Zjnu Stadium

题目大意：排座位，给出关系，B要在A后x位，给出许多的关系，求出错误的个数。

题解：加权并查集，注意关系不要弄混了。

#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
", ans); 
    } 
    return 0; 
}