【BZOJ 1202】 [HNOI2005]狡猾的商人

【链接】 我是链接,点我呀:)
【题意】

在这里输入题意

【题解】

每一段相当于pre[y]-pre[x-1]=z 则。 pre[x-1]+z = pre[y]

所以可以用带权并查集来表示这个关系。
即relation[x] = z;

然后就是一道普通的带权并查集题目啦

在做路径压缩的转移的时候。
是relation[x]+=relation[y];
而不是+=relation[祖先]
因为前面一个的影响还没加进去呢。。

【代码】

#include <bits/stdc++.h>
using namespace std;

const int N = 100;

int n,m,rel[N+10],f[N+10];

int ff(int x){
    if (f[x]==x) return x;
    int oldfa = ff(f[x]);
    rel[x]+=rel[f[x]];
    return f[x]=oldfa;
}

int main()
{
    //freopen("D:\rush.txt","r",stdin);
    int T;
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&n,&m);
        for (int i = 0;i <= n;i++) f[i] = i;
        for (int i = 0;i <= n;i++) rel[i] = 0;

        bool ok = true;
        for (int i = 1;i <= m;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            //pre[y]-pre[x-1]=z
            //pre[y] = pre[x-1]+z;
            x--;
            int r1 = ff(x),r2 = ff(y);
            if (r1!=r2){
                f[r1] = r2;
                rel[r1] = z+rel[y]-rel[x];
            }else{
                int temp = rel[x]-rel[y];
                if (temp!=z){
                    ok = false;
                }
            }
        }
        if (!ok){
            puts("false");
        }else{
            puts("true");
        }
    }
    return 0;
}