HDU 3038 How Many Answers Are Wrong

题意：对于一个整数序列，每次指令为a b c，表示序列中从第a项加到第b项的和为c。若某条指令与前面指令所传达的信息矛盾，则视为该指令错误，否则视为该指令正确。给出一串指令，问错误指令的数量为多少。

解法：类似POJ 1182 食物链。用并查集做，每个节点有两个参数，比如对于节点x，一个是f，表示其根节点的编号；另一个是r，表示前x项之和减去前x.f项之和的差值。然后判定就好了。

tag:并查集

/*
 * Author:  Plumrain
 * Created Time:  2013-11-28 08:32
 * File Name: DS-HDU-3038.cpp
 */
#include <iostream>
#include <cstdio>

using namespace std;

struct node{
    int f, r;
};

int n, m, ans;
node a[200005];

int find(int x)
{
    if (x != a[x].f){
        int y = a[x].f;
        a[x].f = find(a[x].f);
        a[x].r = a[x].r + a[y].r;
    }
    return a[x].f;
}

void merge(int ta, int tb, int s, int fa, int fb)
{
    a[fa].f = fb;
    a[fa].r = a[tb].r - a[ta].r - s;
}

bool ok(int ta, int tb, int s, int fa, int fb)
{
    return s == (a[tb].r - a[ta].r); 
}

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

    int ta, tb, s;
    for (int i = 0; i < m; ++ i){
        scanf ("%d%d%d", &ta, &tb, &s);
        -- ta;
        
        int t1 = find(ta), t2 = find(tb);
        if (t1 != t2)
            merge(ta, tb, s, t1, t2);
        else
            if (!ok(ta, tb, s, t1, t2)) ++ ans;
    }
}

int main()
{
    while (scanf ("%d%d", &n, &m) != EOF){
        init();
        printf ("%d
", ans);
    }
    return 0;
}