带权并查集、种类并查集、变形

理解

一般的并查集，维护的信息只有一个元素所在的集合，并能够通过这一点回答两个元素是否在同一个集合中。

带权并查集对每个节点维护一个权值，通常表示这个节点与根节点之间的关系。在同一个集合内，如果知道两个不同节点各自与根节点的关系，那么这两个节点各自与同一个 “标准” 相比得到的信息，有可能告诉我们这两个节点之间的关系。

也就是说，带权并查集相比一般的并查集，维护的信息不再只是两个元素是否有关系（在同一个集合内），还有两个元素有什么关系。由于带权并查集对单元素只维护关于根的权值，因此，这种关系需要能够根据两个元素相较于第三个元素的关系推断出来。

种类并查集则通过另一种方法维护两个元素之间的关系。我们知道，一般的并查集对于两个元素，只能告诉我们这两个元素有关系还是没关系。那么在可能的关系数量不多的情况下，我们可以维护多个并查集，通过一系列询问，完全确定两个元素之间的关系。例如，题目中涉及的关系有 $A，B，C$ 三种，任意两个元素的关系都是其中一种，最多询问两次形如 “$x,y$ 的关系是 $A$ ？“ 可以确定 $x，y$ 的关系。

带权并查集的维护

合并操作只要修改根节点的 $val$，对于这个根节点下的节点，在find过程中更新其 $val$ 的值。

根节点的 $val$ 根据下图所示的方法确定

假设 $x，y$ 的关系为 $val[x]+\Delta=val[y]$，那么就有 $val[x]+val[fx]=\Delta+val[y]$。

至于find函数：

// 若x不与根直接相连，则更新val[x]
int find(int x) {
    if (x == fa[x]) return x;
    int f = fa[x];
    fa[x] = find(f);
    val[x] += val[f];
    return fa[x];
}

注意每次访问 $val$ 前，需要先find一次以确保 $val$ 的值正确。

相关题目

POJ 1988 Cube Stacking

开始每个栈里边都有一个方块，有两种操作，第一个操作M X Y表示把包含 $X$ 方块的栈里边的所有方块都放在 $Y$ 方块的栈上边。第二个操作C X询问 $X$ 方块下边有多少方块。

裸的带权并查集。

POJ1182 食物链

有三类动物 $A，B，C$，捕食关系为 $A\to B,B\to C,C \to A$。

现有 $N$ 个动物，以 $1\dots N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示 $X$ 和 $Y$ 是同类。
第二种说法是”2 X Y”，表示 $X$ 吃 $Y$ 。
此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中 $X$ 或 $ Y$ 比 $N$ 大，就是假话；
3） 当前的话表示 $X$ 吃 $X$，就是假话。

输出假话数量。

• 带权并查集：维护节点与根节点之间的食物关系，$x$ 直接捕食 $y$，可以 ++val[x]，从两个节点相较于根的权值查可以知道这两个节点之间的关系。
• 种类并查集：两个元素要么是同类，要么是捕食，要么是被捕食。维护三个并查集，对某个元素 $x$，三个并查集维护的集合分别是 $x$ 的同类， $x$ 的捕食者， $x$ 的捕食者的捕食者。

HDU 3038 – How Many Answers Are Wrong

现给出 $n$ 个数字组成的序列，编号为 $1\dots n$；

给出 $m$ 个查询，每个查询的答案由 $a,b,s$ 三个数组成，表示从第 $a$ 个数加到第 $b$ 个数的和为 $s$；

但是其中有一些是有矛盾的（或者说错误的），求错误的查询答案有多少个。

trick：半闭半开区间易于合并分割。

题中难以从一个区间的和中减去某个元素的值。可以利用 $[a,b)+[b,c)=[a,c)$，将题目中给出的闭区间改为半闭半开区间。

左端点与右端点的关系为从左端点到右端点的和，由于关系种类太多，只能建带权并查集。

POJ 1456 Supermarket

超市里有 $N$ 个商品.。第 $i$ 个商品必须在保质期(第 $d_i$ 天)之前卖掉，若卖掉可让超市获得 $p_i$的利润。每天只能卖一个商品。现在你要让超市获得最大的利润。

和 Atlantis 有点像。另一种贪心策略：按照价值降序排序，依次考虑每个商品，每个商品尽可能在最后关头卖掉。

类似并查集的维护方法。对每个日期维护指向从它本身开始前一个可用的日期的指针，可以用路径压缩的思想优化跳指针的过程。

ZOJ 3261 Connections in Galaxy War

$N$ 个星球，编号从 $0$ 到 $N-1$。每个星球有一个战斗力 $power$，且这N个星球之间建有一些通道，可以相互联系，在星球大战中，一些星球要向和自己联通的星球中 $power$ 最强且大于自己的星球求救，且在星球大战中会有一些通道被损坏。

两种操作：破坏a和b之间的通道；a星球该向谁求救。

并查集并不支持集合分裂。

trick：离线处理。

正序的分裂，逆序考虑就是合并。读入全部询问。先将整个过程中都没被影响的边维护一下。之后逆序处理各个询问。

Views: 104