[bzoj1202][HNOI2005]狡猾的商人[并查集]

#include <cstdio>#include <iostream>#include<cstring>using namespace std;int w;int n,m;int s,t,v;int fa[102];int v1[102];bool flag;int parent;inline int get(int x){    if (fa[x]==x) return x;    parent=get(fa[x]);    v1[x]+=v1[fa[x]];    fa[x]=parent;    return fa[x];}inline void work(int x,int y,int z){    int xf=get(x);int yf=get(y);    if (xf!=yf)    {        fa[xf]=yf;        v1[xf]=v1[y]-v1[x]-z;    }    else if (v1[y]-v1[x]!=z) flag=true;}int main(){    scanf("%d",&w);    for (register int i=1;i<=w;i++)    {        memset(v1,0,sizeof(v1));        flag=0;        scanf("%d%d",&n,&m);        for (register int j=0;j<=n;j++) fa[j]=j;           for (register int j=1;j<=m;j++)        {            scanf("%d%d%d",&s,&t,&v);            work(s-1,t,v);        }        if (flag) PRintf("false/n");        else printf("true/n");    }    return 0;}