emm...我来加个并查集的新题解吧。。大概就是强行权值并查集一波,,然后在一个集内的话判一下是否合法就可以了
代码量极短
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,f[1000],ff[1000],x,y,z,xx,yy;
bool flag;
int fa(int x){
if (f[x]==x)return x;
int k=f[x],kk=fa(f[x]);ff[x]+=ff[k];//加上父节点的权值然后连接到father
f[x]=kk;return kk;//路径压缩
}
signed main(){
ios::sync_with_stdio(false);
cin>>t;while (t--){
cin>>n>>m;flag=true;
for (int i=0;i<=n;i++)f[i]=i,ff[i]=0;
for (int i=1;i<=m;i++){
cin>>x>>y>>z;x--;xx=fa(x);yy=fa(y);//考虑前缀和数组,x到y的和自然是a[y]-a[x-1],所以x要--
if (xx!=yy){
f[yy]=xx;ff[yy]=ff[x]+z-ff[y];//连边
}else flag&=ff[x]+z==ff[y];//判断是否合法
}if (flag)cout<<"true"<<endl;else cout<<"false"<<endl;
}
}
```