kuangbin_UnionFindD (HDU 3038)

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

int father[200005],sum[200005];
int n,m,ans;
int find(int x)
{
    if(father[x] != x) {
        int tmp = father[x];
        father[x] = find(father[x]);
        sum[x] += sum[tmp];
    }
    return father[x];
}
void merge(int x,int y,int s)
{
    int tx = find(x);
    int ty = find(y);
    if(tx == ty) {
        if(sum[x] - sum[y] != s)
        {
            ans++;
            //printf("tx = %d;ty = %d;\n", tx, ty);
        }
        return;
    }
    else
    {
        father[tx] = ty;
        sum[tx] = sum[y] - sum[x] + s;
    }
}
int main()
{
    while(~scanf("%d%d", &n,&m))
    {
        for(int i = 0; i <= n; ++i)
        {
            father[i] = i;
            sum[i] = 0;
        }
        //printf("father(10) = %d\n",father[10]);
        //printf("find(10) = %d\n",find(10));
        ans = 0;
        while(m--)
        {
            int x, y, s;
            scanf("%d%d%d", &x, &y, &s);
            x--;
            merge(x, y, s);
        }
        printf("%d\n",ans);
    }
    return 0;
}