带权并查集 | 加个权值

带权并查集啦啦啦

太厉害了

就是合并的时候加个权值，找祖父时加个权值。

找祖父

int find(int a)
{
    if(a!=fa[a])
    {
        int t=fa[a];
        fa[a]=find(fa[a]);
        val[a]+=val[t]; // 跟新 这个节点到 祖父的 权值 
    }
    return fa[a];
}

合并

    int l=find(a);
            int r=find(b);
            if(l!=r)
            {
                fa[l]=r;
                val[l]=-val[a]+c+val[b];   //跟新权值 
            }
            else
            {
                if(val[a]-val[b]!=c) ans++;// 解决问题 小的节点到 祖父的权值 大 
            }
        }

例题：

HDU-3038-How Many Answers Are Wrong

这个题题目的废话比较多，这里简述一下大意：有M个数，不知道它们具体的值，但是知道某两个数之间（包括这两个数）的所有数之和，现在给出N个这样的区间和信息，需要判断有多少个这样的区间和与前边已知的区间和存在矛盾。例如给出区间和[1,4]为20，[3,4]为15，再给出[1,2]为30，显然这个[1,2]的值就有问题，它应该为20-15=5。

View Code

代码：

#include <bits/stdc++.h>
using namespace std;
#define ri register int
const int N=202000;
const int M=40000;
int n,m;
int val[N],fa[N],ans;
int find(int a)
{
    if(a!=fa[a])
    {
        int t=fa[a];
        fa[a]=find(fa[a]);
        val[a]+=val[t]; // 跟新 这个节点到 祖父的 权值 
    }
    return fa[a];
}
int main(){
    while(~scanf("%d%d",&n,&m))
    {
        ans=0;memset(val,0,sizeof val);
        for(ri i=0;i<=n;i++) fa[i]=i;
        for(ri i=1;i<=m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a--;
            int l=find(a);
            int r=find(b);
            if(l!=r)
            {
                fa[l]=r;
                val[l]=-val[a]+c+val[b];   //跟新权值 
            }
            else
            {
                if(val[a]-val[b]!=c) ans++;// 解决问题 小的节点到 祖父的权值 大 
            }
        }
        printf("%d\n",ans);
    }
}

View Code