hdu 3038 How Many Answers Are Wrong（并查集的思想利用）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3038

题意：就是给出n个数和依次m个问题，每个问题都是一个区间的和，然后问你这些问题中有几个有问题，有问题的直接忽略。

每个问题给出a～b之间的和为s，其实就是val(b)-val(a-1)的值为s，这样就容易想到用向量的方法来求解



#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
const int M = 2e5 + 10;
int n , m , f[M] , root[M];
void init() {
    for(int i = 0 ; i <= n ; i++) {
        f[i] = i , root[i] = 0;
    }
}
int find(int x) {
    if(x == f[x])
        return x;
    int tmp = find(f[x]);
    root[x] += root[f[x]];
    return f[x] = tmp;
}
int main() {
    int a , b , s;
    while(scanf("%d%d" , &n , &m) != EOF) {
        init();
        int count = 0;
        for(int i = 1 ; i <= m ; i++) {
            scanf("%d%d%d" , &a , &b , &s);
            a--;
            int x = find(a) , y = find(b);
            if(x == y) {
                if(root[b] - root[a] != s)
                    count++;
            }
            else {
                f[x] = y;
                root[x] = root[b] - root[a] - s;
            }
        }
        printf("%d
" , count);
    }
    return 0;
}