HDU3038【种类并查集】

题意：

给出m组区间[a,b]，以及其区间的和，问有矛盾的有几组；

思路：

种类并查集。

主要是几个关系：同类元素的关系，父亲与儿子的关系，不同类元素的关系；

我们可以类似看作一个前缀和，sum[x]是x到根这段路径上的和，那么根一定是坐标越小的，那么如果说对于同类（同一个集合）的判断就是sum[b]-sum[a-1]是否等于给出值

如果是不同类的话：组合，大的值归到小的去。

考虑区间[x,y]，xx是x的根，yy是y的根

第一种：yy>xx

xx sum[xx]

yy sum[yy]



x sum[x]

        val

y sum[y]

pre[yy]=xx;

sum[yy] = sum[x] + val - sum[y];

第二种：xx>yy

yy sum[yy]

xx sum[xx]



x sum[x]

    val

y sum[y]

pre[xx]=yy;

sum[xx] = sum[y] - sum[x] - val;

在状态压缩的时候，就是一个前缀和嘛，直接把之前的加过来就好了。

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+10;

int sum[N],pre[N],ans,n,m;

int Find(int x)

{

    if(pre[x]==x)

        return x;

    int temp=pre[x];

    pre[x]=Find(temp);

    sum[x]+=sum[temp];

    return pre[x];

}

void Merge(int x,int y,int val)

{

    int xx=Find(x);

    int yy=Find(y);

    if(xx>yy)

    {

        pre[xx]=yy;

        sum[xx]=sum[y]-sum[x]-val;

    }

    else if(xx<yy)

    {

        pre[yy]=xx;

        sum[yy]=sum[x]+val-sum[y];

    }

    else{

        if(sum[y]-sum[x]!=val)

            ans++;

    }

}

int main()

{

    while(~scanf("%d%d",&n,&m))

    {

        for(int i=0;i<=n;i++)

        {

            sum[i]=0;

            pre[i]=i;

        }

        ans=0;

        while(m--)

        {

            int x,y,val;

            scanf("%d%d%d",&x,&y,&val);

            Merge(x-1,y,val);

        }

        printf("%d\n",ans);

    }

    return 0;

}

巴特西

HDU3038【种类并查集】

最新文章

热门文章