在并查集的同时维护到第一个点的距离
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using
namespace std;
#define maxn 200
int f[maxn];
int t[maxn];
int
get(int x){
if(f[x]==x)return x;
int l=get(f[x]);
t[x]+=t[f[x]];
return f[x]=l;
}
int n,m;
int w;
int
main(){
scanf("%d",&w);
while(w--){
bool
p=0;
scanf("%d%d",&n,&m);
for(int
i=0;i<=n;i++)f[i]=i,t[i]=0;
for(int i=1;i<=m;i++){
int
a,b,c;
scanf("%d%d%d",&a,&b,&c);
int
x=get(a-1);
int y=get(b);
if(x==y){
if(t[a-1]+c!=t[b])p=1;
}else{
f[y]=x;
t[y]=-t[b]+t[a-1]+c;
}
}
if(p==1)printf("false\n");
else
printf("true\n");
}
}
bzoj 1202: [HNOI2005]狡猾的商人 并查集,布布扣,bubuko.com
bzoj 1202: [HNOI2005]狡猾的商人 并查集
原文：http://www.cnblogs.com/wangyucheng/p/3639106.html