python/TangDou/AcWing/2128_BCJ.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
bool flag;
int d[N]; //到根的距离
int p[N]; //并查集数组
int n, m;
//带权并查集模板
int find(int x) {
    //点权的理解：每个点到根的距离
    if (p[x] == x) return x; //自己是老大，返回自己
    int root = find(p[x]);   //通过自己父亲找老大
    d[x] += d[p[x]];         //点权在路径压缩过程中，需要加上父亲的点权
    return p[x] = root;      //路径压缩
}

//合并时进行d[px]修改是关键
void join(int x, int y, int w) {
    int px = find(x), py = find(y);
    if (px != py) {
        p[px] = py;              //加入py家族
        d[px] = d[y] - d[x] + w; //更新px的距离
    } else if (d[x] - d[y] != w)
        flag = true;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        //多组测试数据，需要清空
        flag = false;
        memset(d, 0, sizeof(d)); //初始化每个节点到根的距离

        cin >> n >> m;
        //初始化并查集,注意此处从0开始！原因是前缀和从0开始，比如1-3月，那么其实是加入了0号家族
        for (int i = 0; i <= n; i++) p[i] = i, d[i] = 0;
        // m组条件
        while (m--) {
            int s, t, v; //开始月份，结束月份，区间内的
            cin >> s >> t >> v;
            //利用前缀和思想，检查从s到t这个区间内收益是不是v
            join(s - 1, t, v);
        }
        //有冲突
        if (flag)
            puts("false");
        else //无冲突
            puts("true");
    }
    return 0;
}