欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

带权并查集(hdoj 3038)

程序员文章站 2022-03-15 22:40:54
...

阿伟学了三天的带权并查集emmm,基本内容还算是掌握了
带权并查集最重要的还是偏移量的理解,以及偏移量更新的方法,这里主要应用了向量的知识。用例题来说明吧。

hdoj 3038 How Many Answers Are Wrong

题目大意: TT和FF在做一个游戏(boring)。提供一些数的下标 i 和 j ,以即a[i],a[i+1],a[i+2]…,a[j]的和,判断给出的是否是正确答案,如果判断不了就当做正确答案。

题解: 此题要用到带权并查集,也就是每个元素到根节点的距离,即偏移量。用dis表示。初始化为0。偏移量的计算用 向量 比较方便。

当两个点的根节点不相同时,需要将两个节点进行合并,此时设a的根节点为ra,b的根节点为rb,a到b的距离为输入给出的c,因为此时无法判断所得的和是否正确,因此默认为正确答案。进行两个节点的合并,将rb作为ra的根节点,则dis[ra]的计算方法如图所示(向量的应用)
带权并查集(hdoj 3038)
当两个节点的根节点相同时,这时就可以判断给出的值是否是正确答案了,因为在寻找根节点的时候已经将每个节点都挂在根节点上,形式都如下图所示,因此在计算所给的两点之间的和时,只用dis[a]-dis[b]即可,具体如图(向量)。
带权并查集(hdoj 3038)
到这里,偏移量就结束了,再看看如何寻找根节点。

在之前,我的查找根节点都是这样写的emmm

int find_root(int x)
{
    while(parent[x]!=x)
        x=parent[x];
    return x;
}

这么写只是从上到下查找根节点,并不会路径压缩,即就算6->7->8,查找到6的根节点是8,并不会把6直接挂到8上面,即不会进行路径压缩。
然后看了dalao的代码

int find_root(int x)
{
    return parent[x]==x ? x : parent[x]=find_root(parent[x]);
}

WTF!!!(对8起,我爆粗口了)
这段代码也就是这样的:

int find_root(int x)
{
    if(parent[x]==x)
        return x;
    else
        return parent[x]=find_root(parent[x]);
}

在查找根节点的时候已经将它挂在根节点上了,也就是如图的亚子~
带权并查集(hdoj 3038)
Soga~~
从图中也能看出来,在每次递归的时候都需要更新dis的值,即加上其父节点的dis值。。
因此find_root函数就可以这么表示:

int find_root(int x)
{
    if(parent[x]!=x)
    {
        int tmp=parent[x];
        parent[x]=find_root(parent[x]);//递归查找根节点
        dis[x]+=dis[tmp];//更新dis
    }
    return parent[x];
}

最后贴上AC代码:

#include <iostream>
using namespace std;
int n,m;
int parent[200010],dis[200010];
void init()
{
    for(int i=0;i<=n;i++)
    {
        parent[i]=i;
        dis[i]=0;
    }
}
int find_root(int x)
{
    if(parent[x]!=x)
    {
        int tmp=parent[x];
        parent[x]=find_root(parent[x]);//递归查找根节点
        dis[x]+=dis[tmp];//更新dis
    }
    return parent[x];
}
int main()
{
    while(cin>>n>>m)
    {
        init();
        int ans=0;
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            a--;
            int aa=find_root(a);
            int bb=find_root(b);
            //判断两点的根节点是否相同,如果相同则
            //说明两点都与根节点有关,可以直接判断是否是错误答案
            //如果根节点不相同,则说明无法从已知条件判断是否是错误答案
            //也就是没必要判断,将两点合并即可
            if(aa==bb)
            {
                if(dis[a]-dis[b]!=c)
                    ans++;
            }
            else
            {
                parent[aa]=bb;
                dis[aa]=-dis[a]+c+dis[b];//向量计算
            }
        }
        cout<<ans<<endl;
    }
}
相关标签: 并查集