题目

Code

f a [ x ] fa[x] fa[x]表示 x x x路径压缩后的父亲
d [ x ] d[x] d[x]表示 x x x到 f a [ x ] fa[x] fa[x]的距离（有向， f a [ x ] fa[x] fa[x]到 x x x的距离为 − d [ x ] -d[x] −d[x]）

#include<bits/stdc++.h>
using namespace std;
const int N=102;
int n,m,x,y,z,i,rx,ry,fa[N],d[N],T;
bool fl;
int find(int x){
	if (x==fa[x]) return x;
	int t=find(fa[x]);//更新了d[fa[x]],fa[x]还没更新
	d[x]+=d[fa[x]];
	return fa[x]=t;
}
int main(){
	scanf("%d",&T);
	for (;T--;){
		scanf("%d%d",&n,&m);
		for (i=0;i<=n;i++) fa[i]=i,d[i]=0;
		fl=1;
		for (i=1;i<=m;i++){
			scanf("%d%d%d",&x,&y,&z);
			x--;
			rx=find(x),ry=find(y);
			if (rx!=ry){
				fa[rx]=ry;
				d[rx]=d[y]-d[x]+z;//rx->ry=(x->rx->ry->y)-(x->rx)-(ry->y)=z-d[x]+d[y]
			}else if (d[x]-d[y]!=z) fl=0;
		}
		puts(fl?"true":"false");
	}
}