H. The Third Letter

题目链接：Problem - H - Codeforces

题目大意：

一共t 组数据。对于每组数据：

第一行给定 n 和 m，表示有 n 个人和 m 个要求。每个人都站在数轴上的一个整数点上（可以在负半轴上）。

然后的 m 行，每行一个要求。每个要求包含 ai​,bi​ 和 wi​，表示第 ai 个人要站在第 bi​ 个人前方的第 wi​ 个位置（如果 wi​ 是负数，则第 ai​ 个人要站在第 bi​ 个人后方的第 −wi​ 个位置）。问是否存在满足要求的方案。

1<=t≤100,∑n ≤ 2e5, m ≤ n, −1e9 ≤ di ≤ 1e9

    带权并查集模板题

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

using i64 = long long;
using i128 = __int128;
using ui64 = unsigned long long;
//模板
struct DSU{
    int n;
    vector<int> tree;
    vector<i64> dist;

    DSU(){}
    DSU(int n){
        innt(n);
    }

    void innt(int n){
        this->n = n;
        tree.resize(n);
        dist.assign(n,0LL);
        for(int i=0; i<n; i++) {
            tree[i] = i;
        }
    }
    int find(int x){
        if(tree[x] != x) {
            int fx = find(tree[x]);//一定要先路径压缩
            dist[x] += dist[tree[x]];
            tree[x] = fx;
        }
        return tree[x];
    }
    bool merge(int a,int b, i64 val){
        int fa = find(a);
        int fb = find(b);
        if(fa == fb)return false;
        dist[fa] = dist[b] - dist[a] + val;
        tree[fa] = fb;
        return true;
    }
    bool same(int a, int b){
        return find(a) == find(b);
    }
    i64 ask(int a, int b){
        return dist[a] - dist[b];
    }
};

void solve(){
    int n, m;
    cin >> n >> m;
    DSU dsu = DSU(n);
    bool ok = true;
    for(int i=0; i<m; i++) {
        int a, b, val;
        cin >> a >> b >> val;
        if(!ok)continue;
        a--, b--;
        if(!dsu.merge(a, b, val)) {
            if(dsu.ask(a, b) != val) {
                cout << "NO\n";
                ok = false;
            }
        }
    }
    if(ok) {
        cout << "YES\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

感谢大家的收看与点赞， 欢迎大佬指正。