一道差分约束.
但是我横看竖看, 只从字缝里看到了"并查集"三个大字.
很明显嘛, 什么判断真假, 什么前缀和关系传递, 不是明摆着的带权并查集吗?
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1e2 + 10;
const int MAXM = 1e3 + 10;int W, N, M;namespace ufs
{int fa[MAXM], d[MAXM];void init(){memset(d, 0, sizeof(d));for(int i = 0; i <= N; i++) fa[i] = i;}int findfa(int x){if(fa[x] == x) return x;int tmp = findfa(fa[x]);d[x] += d[fa[x]];return fa[x] = tmp;}inline bool unite(int u, int v, int c){if(u > v) swap(u, v);int x = findfa(u), y = findfa(v);if(x == y) return c == (d[u] - d[v]);if(x < y) {fa[x] = y, d[x] = d[v] + c - d[u];return true;} else{fa[y] = x, d[y] = d[u] - c - d[v];return true;}}
}int main()
{//freopen("p2294.in", "r", stdin);cin>>W;while(W--){cin>>N>>M;bool flag = true; ufs::init();for(int i = 1, u, v, c; i <= M; i++){scanf("%d%d%d", &u, &v, &c);if(!flag) continue;if(!ufs::unite(u - 1, v, c)) flag = false;}if(flag) puts("true");else puts("false");}return 0;
}