HDU 3047

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

和hdu 3038以及poj那个食物链一样，都是带权并查集，此题做法和hdu 3038完全相同，具体操作看上篇博客

这题原来写过，但是没过，直接改的原来代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
#include <cmath>

using namespace std;

#define MAX_N 50005

int par[MAX_N];//父亲 
int rank[MAX_N];//树的高度 

void INIT(int n){
    for(int i=0;i<=n;i++){
        par[i]=i;
        rank[i]=0;
    }
}

int n,m;

int find(int x){
    if(par[x]==x){
        return x;
    }
    else{
        int temp=par[x];
        par[x]=find(par[x]);
        rank[x]+=rank[temp];
        return par[x];
    }
}

void solve(){
    int ans=0;
    while(m--){
        int x,y,d;
        scanf("%d%d%d",&x,&y,&d);
        int xp=find(x);
        int yp=find(y);
        if(xp==yp){
            if(rank[y]-rank[x]!=d)ans++;
        }
        else{
            par[yp]=xp;
            rank[yp]=-rank[y]+d+rank[x]; 
        } 
    }
    printf("%d
",ans);
}

int main(){
    while(~scanf("%d%d",&n,&m)){
        INIT(n);
        solve();
    }
    return 0;
}