带权并查集、种类并查集、变形
理解
一般的并查集,维护的信息只有一个元素所在的集合,并能够通过这一点回答两个元素是否在同一个集合中。
带权并查集对每个节点维护一个权值,通常表示这个节点与根节点之间的关系。在同一个集合内,如果知道两个不同节点各自与根节点的关系,那么这两个节点各自与同一个 “标准” 相比得到的信息,有可能告诉我们这两个节点之间的关系。
也就是说,带权并查集相比一般的并查集,维护的信息不再只是两个元素是否有关系(在同一个集合内),还有两个元素有什么关系。由于带权并查集对单元素只维护关于根的权值,因此,这种关系需要能够根据两个元素相较于第三个元素的关系推断出来。
种类并查集则通过另一种方法维护两个元素之间的关系。我们知道,一般的并查集对于两个元素,只能告诉我们这两个元素有关系还是没关系。那么在可能的关系数量不多的情况下,我们可以维护多个并查集,通过一系列询问,完全确定两个元素之间的关系。例如,题目中涉及的关系有 $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