带权并查集 POJ 1182 食物链 & HDU 3047 Zjnu Stadium - dblank

带权并查集 POJ 1182 食物链 & HDU 3047 Zjnu Stadium

带权并查集和普通并查集最大的区别在于带权并查集合并的是可以推算关系的点的集合(可以通过集合中的一个已知值推算这个集合中其他元素的值)。而一般并查集合并的意图在于这个元素属于这个集合。带权并查集相当于把“属于”的定义拓展了一下,拓展为有关系的集合。
POJ 1182 食物链:

用Rank[i] = 1, 表示 i 吃 i 的祖先节点,Rank[i] = 0 表示i 和i 的祖先是同一类,Rank[i] = 2 表示i的祖先吃i。

在这个树里面,把每条边看做一条向量的话,就可以找到压缩和合并的Rank的变化。


#include<bits/stdc++.h>
#pragma comment(linker, "/STACK:102400000,102400000")
#define endl '\n'
using namespace std;
const double eps = 1e-10, pi = acos(-1.0);
const int inf = 0x3f3f3f3f, N = 100000 + 200, Mod = 110119;
typedef long long  ll;
int root[N], rank[N], n, m;
void init()
{
    for(int i = 0; i<n; i++)
        root[i] = i, rank[i] = 0;
}
int Find(int x)
{
    if(x == root[x])
        return x;
    int pre = root[x];
    root[x] = Find(root[x]);
    rank[x] = (rank[x] + rank[pre])%3;
    return root[x];
}
void join(int d, int u, int v)
{
    int x = Find(u), y = Find(v);
    if(x == y) return ;
        root[x] = y;
    rank[x] = (rank[v] + d -  rank[u] + 3)%3;
    return ;
}
bool istrue(int d, int u, int v)
{
    int x  = Find(u), y = Find(v);
    if(u > n || v > n || d == 2 && u == v)
        return false;
    if(x != y)
        return true;
    else
    {
        return rank[u] ==  (rank[v] + d + 2)%3;
    }
}
int main()
{
    int d, u, v;
    scanf("%d%d", &n, &m);
    init();
    int ans = 0;
    while(m--)
    {
        scanf("%d%d%d", &d, &u, &v);
        if(istrue(d, u, v))
            join(d-1, u, v);
        else ans ++;
    }
    printf("%d\n", ans);
    return 0;
}

同样是用rank表示到祖先节点的距离。

#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#pragma comment(linker, "/STACK:102400000,102400000")
#define endl '\n'
using namespace std;
const double eps = 1e-10, pi = acos(-1.0);
const int inf = 0x3f3f3f3f, N = 100000 + 200, Mod = 110119;
typedef long long  ll;
int root[N], Rank[N], n, m, ans;
void init()
{
    for(int i = 0; i<=n; i++)
        root[i] = i, Rank[i] = 0;
    ans = 0;
}
int Find(int x)
{
    if(x == root[x])
        return x;
    int pre = root[x];
    root[x] = Find(root[x]);
    Rank[x] = (Rank[x] + Rank[pre])%300;
    return root[x];
}
void join(int d, int u, int v)
{
    int x = Find(u), y = Find(v);
    root[y] = x;
    Rank[y] = (Rank[u] + d - Rank[v] + 300)%300;
}
int istrue(int d, int u, int v)
{
    int x = Find(u), y = Find(v);
    if(x != y) return 1;
    return Rank[v] == (Rank[u] + d)%300;
}
int main()
{
    int u, v, d;
    while(~scanf("%d%d", &n, &m))
    {
        init();
        while(m--)
        {
            scanf("%d%d%d", &u, &v, &d);
            if(istrue(d, u, v))
                join(d, u, v);
            else ans ++;
        }
        printf("%d\n", ans);
    }
    return 0;
}

相关文章

仅有 1 条评论
  1. Aburedorge

    Four to five portions of this veggie juice must be consumed every week to obtain the desired result. Once you discover the top natural treatments, it is possible to once again have full charge of your sexual pleasures.
    http://www.generiqueviagrafr.fr/vente-viagra-usa

    Aburedorge 回复
发表新评论