python/TangDou/AcWing/HowManyAnswersAreWrong.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 200005;
int p[N];
int sum[N];     //权边

//标准的带路径压缩的并查集,查找祖先
int find(int x) {
    if (x != p[x]) {
        int i = p[x];
        p[x] = find(p[x]);
        sum[x] += sum[i]; //这里是权累加，就是在路径压缩过程中处理了权的问题
    }
    return p[x];
}

// 原题链接
// http://acm.hdu.edu.cn/showproblem.php?pid=3038
int main() {
    //输入+输出重定向
    freopen("../AcWing/N5/HowManyAnswersAreWrong.txt", "r", stdin);
    int m, n;
    int ans;
    while (scanf("%d%d", &m, &n) != EOF) {
        //初始化并查集
        for (int i = 0; i <= m; i++) {
            p[i] = i;//是有个范围的，每个都是独立的
            sum[i] = 0;  //初始的权是零
        }
        ans = 0;
        //处理数据
        while (n--) {
            int l, r, value;
            cin >> l >> r >> value;
            l--;
            int fl = find(l);
            int fr = find(r);
            if (fl == fr) {
                if ((sum[l] - sum[r]) != value) {
                    ans++;
                }
            } else {
                p[fl] = fr;//并查集的合并
                sum[fl] = -sum[l] + sum[r] + value;//权值修改
            }
        }
        cout << ans << endl;
    }
    //关闭文件
    fclose(stdin);
    return 0;
}