带权并查集求助

题目总版

ppip @ 2022-04-25 20:57:01

Link

题目大意:给定一堆 (x,y,z)(1\leq x\leq n,1\leq y\leq m),表示 v_x+v_{y+n}=z,问后面信息是否与前面有矛盾。

代码(删除了不必要元素):

#include <bits/stdc++.h>
using namespace std;
const int MAXN{1000};
int f[MAXN*2+5],dis[MAXN*2+5];
int getf(int x)
{
    if (f[f[x]]==f[x]) return f[x];
    getf(f[x]);
    dis[x]+=dis[f[x]];
    return f[x]=f[f[x]];
}
void merge(int x,int y,int z)
{
    dis[f[x]]=z-dis[x]+dis[y];
    f[f[x]]=f[y];
}
int main()
{
    int n,m,k;scanf("%d %d %d",&n,&m,&k);
    for (int i{1};i<=n+m;++i)
    {
        f[i]=i;
        dis[i]=0;
    }
    for (int i{1};i<=k;++i)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        if (getf(x)==getf(y+n)&&dis[x]-dis[y+n]!=z) {printf("No\n");return 0;
        else merge(x,y+n,z);
    }
    printf("Yes\n");
    return 0;
}

显然,这份代码维护 dis(x)=v_x-root。但是这样的话,这份代码不就是把输入的信息当成 v_x-v_{y+n}=z 来做的吗,为什么能 AC?


by qiuzx @ 2022-04-26 22:36:20

把所有>n的位置取反就是等价的


|