题解 P2024 【食物链】
Sooke
2017-06-30 18:55:53
### 重写于 2018.9.13,并修改代码码风(以前的码风真是丑啊qwq)
本题解适合于并查集初学者,建议嫌文章冗长的巨佬们阅读其他题解。
-------------
### 引入
并查集能维护连通性、传递性,通俗地说,`亲戚的亲戚是亲戚`。
然而当我们需要维护一些对立关系,比如 `敌人的敌人是朋友` 时,正常的并查集就很难满足我们的需求。
这时,`种类并查集`就诞生了。
常见的做法是将原并查集扩大一倍规模,并划分为两个种类。
在同个种类的并查集中合并,和原始的并查集没什么区别,仍然表达`他们是朋友`这个含义。
考虑在不同种类的并查集中合并的意义,其实就表达 `他们是敌人` 这个含义了。
按照并查集美妙的 `传递性`,我们就能具体知道某两个元素到底是 `敌人` 还是 `朋友` 了。
至于某个元素到底属于两个种类中的哪一个,由于我们不清楚,因此两个种类我们都试试。
具体实现,详见 `P1525 关押罪犯`。
----------------
### 概念解释
再来看本题,每个动物之间的关系就没上面那么简单了。
对于动物 $x$ 和 $y$,我们可能有 $x$ 吃 $y$,$x$ 与 $y$ 同类,$x$ 被 $y$ 吃。
但由于关系还是明显的,$1$ 倍大小、$2$ 倍大小的并查集都不能满足需求,$3$ 倍大小不就行了!
类似上面,我们将并查集分为 $3$ 个部分,每个部分代表着一种动物种类。
设我们有 $n$ 个动物,开了 $3n$ 大小的种类并查集,其中 $1 \sim n$ 的部分为 $A$ 群系,$n + 1 \sim 2n$ 的部分为 $B$ 群系,$2n + 1 \sim 3n$ 的部分为 $C$ 群系。
我们可以认为 $A$ 表示中立者,$B$ 表示生产者,$C$ 表示消费者。此时关系明显:$A$ 吃 $B$,$A$ 被 $C$ 吃。
当然,我们也可以认为 $B$ 是中立者,这样 $C$ 就成为了生产者,$A$ 就表示消费者。(还有 $1$ 种情况不提及了)
联想一下 $2$ 倍大小并查集的做法,不难列举出:当 $A$ 中的 $x$ 与 $B$ 中的 $y$ 合并,有关系 $x$ 吃 $y$;当 $C$ 中的 $x$ 和 $C$ 中的 $y$ 合并,有关系 $x$ 和 $y$ 同类等等……
但仍然注意了!我们不知道某个动物属于 $A$,$B$,还是 $C$,我们 $3$ 个种类都要试试!
也就是说,每当有 $1$ 句真话时,我们需要合并 $3$ 组元素。
容易忽略的是,题目中指出若 $x$ 吃 $y$,$y$ 吃 $z$,应有 $x$ 被 $z$ 吃。
这个关系还能用种类并查集维护吗?答案是可以的。
若将 $x$ 看作属于 $A$,则 $y$ 属于 $B$,$z$ 属于 $C$。最后,根据关系 $A$ 被 $C$ 吃可得 $x$ 被 $z$ 吃。
既然关系满足上述传递性,我们就能放心地使用种类并查集来维护啦。
----------------------
### 图片解释
理论太难懂?那就结合数据和图片来解释吧!
假如我们有以下的输入数据:
```cpp
4 5
1 1 3
2 2 4
2 3 2
1 1 4
2 2 1
```
因为涉及 4 个动物($n = 4$),所以构建初始并查集如下图:
![](https://cdn.luogu.com.cn/upload/pic/6104.png)
先看第 $1$ 句话:动物 $1$ 和 $3$ 是同类的。
我们可以在 $3$ 个群系中分别给 $1$ 和 $3$ 的集合合并,以表示动物 $1$ 和 $3$ 是一定友好的。
![](https://cdn.luogu.com.cn/upload/pic/6105.png)
再看第 $2$ 句话:动物 $2$ 吃 $4$。
显然这不是矛盾的。但我们不知道 $2$ 和 $4$ 对应 $A$, $B$,$C$ 中的哪个,所以我们只能根据 $A$ 吃 $B$,合并 $A$ 群系中的 $2$ 和 $B$ 群系中的 $4$;再根据 $B$ 吃 $C$ 和 $C$ 吃 $A$,作出对应的处理。结果如下所示:
![](https://cdn.luogu.com.cn/upload/pic/6106.png)
接着看第 $3$ 句话:动物 $3$ 吃 $2$。这是句真话,具体的真假话判断方法看下面两句话。我们暂且先作出以下处理:
![](https://cdn.luogu.com.cn/upload/pic/6107.png)
第 $4$ 句话中,表明 $1$ 和 $4$ 是同类动物。此时我再解释如何判断话的真假。
对于同类动物,我们转换一下,如果我们知道 $1$ 不吃 $4$ 且 $4$ 不吃 $1$,他们不就同类了吗?
好,那我们的任务就变成:如何判断动物 $x$ 吃动物 $y$?
反观第 $2$ 句话,我们知道如果要表示动物 $x$ 吃动物 $y$,只要根据 $A$ 吃 $B$,把 $A$ 群系中的 $x$ 和 $B$ 群系中的 $y$ 合并即可。另外 $2$ 次合并暂不讨论。
那反过来,如果 $A$ 群系中的 $x$ 已经和 B 群系中的 $y$ 在同一集合中了,不就表示了动物 $x$ 吃动物 $y$ 吗?
于是,我们看到上面那张图,$B$ 群系中的 $1$ 按照并查集的递归操作,找出自己的终极上级是 $A$ 群系中的 $4$。
分析其含义,属于 $B$ 群系的 $1$ 已经与 $A$ 群系的 $4$,应有 $4$ 吃 $1$,而非同类。第 $4$ 句话是假的。
那么第 $5$ 句话,$2$ 吃 $1$。我们需要判断 $2$ 和 $1$ 是否是同类并且 $2$ 是否被 $1$ 吃即可。
判断是否同类,我们同样可以反过来:判断在同个群系中的 $2$ 和 $1$ 的集合是否已经合并。
得出 $2$ 和 $1$ 不是同类后,我们再看 $1$ 是否吃 $2$。看图,$A$ 群系中的 $1$ 和 $B$ 群系中的 $2$ 在同一集合中。
得出 $1$ 吃 $2$。第 $5$ 句话也是假话。
因此,答案就是有两句假话。输出 $2$,问题完美解决。
---------------------------
### 注意事项
- 种类并查集求的并非具体种类,而是关系!
- 在代码过程中,不要忘了特判编号大于 $n$ 的情况!
---------------------------
### 代码实现
如果还没有理解,只能使用最终办法了,上程序!
(当然我还是希望各位摸清种类并查集的本质,灵活运用)
```cpp
#include <cstdio>
inline int read() {
char c = getchar(); int n = 0;
while (c < '0' || c > '9') { c = getchar(); }
while (c >= '0' && c <= '9') { n = (n << 1) + (n << 3) + (c & 15); c = getchar(); }
return n;
}
const int maxN = 100005;
int n, m, ans, fa[maxN * 3];
int find(int u) { return fa[u] == u ? u : fa[u] = find(fa[u]); }
int main() {
n = read(), m = read();
for (int i = 1; i <= n * 3; i++) { fa[i] = i; }
for (; m; m--) {
int opt = read(), u = read(), v = read();
if (u > n || v > n) { ans++; continue; }
if (opt == 1) {
if (find(u + n) == find(v) || find(u) == find(v + n)) { ans++; }
else {
fa[find(u)] = find(v);
fa[find(u + n)] = find(v + n);
fa[find(u + n + n)] = find(v + n + n);
}
} else {
if (find(u) == find(v) || find(u) == find(v + n)) { ans++; }
else {
fa[find(u + n)] = find(v);
fa[find(u + n + n)] = find(v + n);
fa[find(u)] = find(v + n + n);
}
}
}
printf("%d\n", ans);
return 0;
}
```
-----------------------------
### 撰文不易,不适轻喷!