带权并查集--hdu3047 ZJnu stadium

风骨散人Chiam

发布于 2020-10-28 10:52:42

3220

发布于 2020-10-28 10:52:42

文章被收录于专栏：CSDN旧文

题意：给出一个n,m,n表示的是有n 个人，m表示的是有m 对关系：接下来输入的就是这m对关系，a,b,x；表示的是a，b相距x个距离；然后判断输入的是否与这个数的上面的数信息一致，输出不一致的数目；

思路：用一个dist[ ]数组记录他到他的祖先的距离；然后对并查集合并的时候将rb的祖先赋给ra，然后就要对dist[rb]的值进行重新赋值，公式为dist[ rb ] = dist[a] + x - dist[b],公式推导可以见下面这张图：

其中为了在找到他的祖先的的同时更新他们的各个dist【】的值，运用了递归；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000 + 10;
ll dist[maxn];
ll n,m;
ll father[maxn];
void Init()
{
    for(int i = 1; i <= n ; i ++)
    {
        dist[i] = 0;
        father[i] = i;
    }
}
ll finds(ll x)
{
    if(father[x] == x)
        return x;
    int t = father[x];
    father[x] = finds(father[x]);
    dist[x] += dist[t];
    return father[x];
}
void unions(ll a,ll b,ll ra,ll rb,ll distance)
{
    father[rb] = ra;
    dist[rb] = dist[a] + distance - dist[b];
}
int main()
{
    while( ~ scanf("%I64d%I64d",&n,&m) )
    {
        Init();
        ll ans = 0;
        for(int i = 1; i <= m ; i ++)
        {
            ll a,b,distance;
            scanf("%I64d%I64d%I64d",&a,&b,&distance);
            ll ra = finds(a);
            ll rb = finds(b);
            if(ra == rb)
            {
                if(dist[b] - dist[a] != distance)
                    ans ++;
            }
            else unions(a,b,ra,rb,distance);
 
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/04/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除

递归