HDU 3038 How Many Answers Are Wrong

传送门：

 

解题思路：

这是一道并查集的题，用了一点向量的知识进行和并。

推荐：http://www.cnblogs.com/liyinggang/p/5327055.html

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn=200000+10;
int f[maxn],r[maxn];

int findfa(int x){
    if(f[x]==x)
        return x;
    int t=f[x];
    f[x]=findfa(f[x]);
    r[x]=r[t]+r[x];
    return f[x];
}

void unit(int x,int y,int w){
    int fx=findfa(f[x]);
    int fy=findfa(f[y]);

    if(fx==fy) return;
    else{
        f[fy]=fx;
        r[fy]=r[x]+w-r[y];
    }
}

void init(int n){
    for(int i=0;i<=n;i++){
        f[i]=i;
        r[i]=0;
    }
}

int main(){
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF){
    init(n);
    int ans=0;
    while(m--){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        x--;
        if(findfa(x)==findfa(y)){
            if((r[y]-r[x])!=w) ans++;
        }else unit(x,y,w);
    }
    printf("%d
",ans);
    }
}