带权并查集

带权并查集

设cnt[x]为x到本集合代表元素的路径值,在递归寻找代表元素时,如果找到就直接返回,没找到先记录下此时x的fa[x],再让fa[x]被更新,fa[x]被更新也意味着fa[x]到代表元素的cnt[fa[x]]被更新了,则此时再用cnt[fa[x]]更新cnt[x],便完成了路径更新。
核心代码

inline int f(int x) {
    if(x ^ fa[x]) {
        int t = fa[x];
        fa[x] = f(fa[x]);
        cnt[x] += cnt[t];
    } 
    return fa[x];
}

How Many Answers Are Wrong HDU - 3038

题意:给出一个区间的长度 N,及 M 个子区间和, 形如:x y z, 表示子区间 [x, y] 的和为 z

如果一个“子区间和”与前面的“子区间和”冲突,即为错误(而且这个“子区间和”将在接下来的判断中被忽略)。

求总错误个数。

判断输入的两个点,如果在相同集合,则检查两点距离是否为之前已确定的距离

如果在不同集合,就合并两个集合。

画图有,fx -> fy = y -> fy - y -> fx,而 y -> fx = x -> fx - x -> y;

则fx -> fy = y -> fy + x->y - x ->fx;

所以 cnt[fx] = cnt[y] - cnt[x] + z;

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <cstring>
#include <algorithm>
#define rint register int
#define ll long long
#define lson x<<1
#define rson x<<1|1
#define mid ((st[x].l + st[x].r) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x)
{
    int f = 1;x = 0;
    char c = getchar();
    for(; c < '0' || c > '9' ; c = getchar()) if(c=='-') f = -1;
    for(;'0' <= c && c <= '9'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
    x *= f;
}
template <typename xxx> inline void print(xxx x)
{
    if(x < 0) {
        putchar('-');
        x = -x;
    }
    if(x > 9) print(x/10);
    putchar(x % 10 + '0');
}
const int inf = 0x7fffffff;
const int maxn = 200100;
const int mod = 1000000007;
int n,m; 
int fa[maxn];
int cnt[maxn];//自身到集合代表的权值 
inline int f(int x) {
    if(x ^ fa[x]) {
        int t = fa[x];
        fa[x] = f(fa[x]);
        cnt[x] += cnt[t];
    } 
    return fa[x];
}
int main()
{
    while(~scanf("%d%d",&n,&m)) {
        for(rint i = 1;i <= n; ++i) {
            fa[i] = i;
            cnt[i] = 0;
        }
        int ans = 0;
        for(rint i = 1;i <= m; ++i) {
            int x,y,z;
            read(x);read(y);read(z);
            --x;
            int fx = f(x);
            int fy = f(y);
            if(fx == fy) {
                if(cnt[x] - cnt[y] != z) ++ans; 
            }   
            else {
                fa[fx] = fy;
                cnt[fx] = cnt[y] - cnt[x] + z; 
            }
        }
        print(ans);putchar('\n');
    }
}
/*

*/
相关文章
相关标签/搜索