bzoj1202--帶權並查集+前綴和，bzoj1202--前綴

bzoj1202--帶權並查集+前綴和，bzoj1202--前綴

http://www.lydsy.com/JudgeOnline/problem.php?id=1202

      記s[i]=a[1]+a[2]+...+a[i]，即s[i]為前綴和。再令v[i]=s[f[i]]-s[i]，其中f[i]為i的父親。對於每個讀入的x,y,k，將x,y視為結點，如果x與y的根結點相同，因為v[y]-v[x]=s[f[y]]-s[y]-s[f[x]]-s[x]且f[y]=f[x]，所以v[y]-v[x]就是區間[x,y]的和，所以只需要判斷v[y]-v[x]是否等於k就可以了。如果x與y的根結點不相同，合並兩個節點並更新信息。

#include<cstdio>
#include<cstring>
using namespace std;
int n,i,j,m,f[101],w,x,y,k,v[101];
bool flag;
int find(int x){
    if(x==f[x])return x;
    int tmp=f[x];                     //記錄原來的父親
    f[x]=find(f[x]);
    v[x]+=v[tmp];                     //更新結點信息
    return f[x];
}
bool union1(int x,int y,int k){
    int fx=find(x),fy=find(y);
    if(fx==fy){
        if(v[y]-v[x]!=k)return 0;
    }else{
        f[fy]=fx;
        v[fy]=k-v[y]+v[x];             //更新結點信息
    }
    return 1;
}
int main()
{
    scanf("%d",&w);
    while(w--){
        memset(v,0,sizeof(v));
        flag=0;
        scanf("%d%d",&n,&m);
        for(i=0;i<=n;i++)f[i]=i;
        for(i=1;i<=m;i++){
            scanf("%d%d%d",&x,&y,&k);
            if(!flag&&!union1(x-1,y,k))flag=1;
        }
        if(flag)printf("false\n");else printf("true\n");
    }
    return 0;
}