[NOI2001] 食物链

题目描述

动物王国中有三类动物 $A,B,C$，这三类动物的食物链构成了有趣的环形。$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。

现有 $N$ 个动物，以 $1\sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。

有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：

• 第一种说法是 1 X Y，表示 $X$ 和 $Y$ 是同类。
• 第二种说法是2 X Y，表示 $X$ 吃 $Y$。

此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话；
• 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
• 当前的话表示 $X$ 吃 $X$，就是假话。

你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。

输入格式

第一行两个整数，$N,K$，表示有 $N$ 个动物，$K$ 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式

一行，一个整数，表示假话的总数。

样例 #1

样例输入 #1

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

样例输出 #1

3

提示

对于全部数据，$1\le N\le 5\times 10^4$，$1\le K\le 10^5$。

题解

扩展域并查集详解

扩展域并查集是一种通过将每个元素拆分成多个域（或状态）来表示复杂关系的并查集方法。在食物链问题中，我们需要处理动物之间的同类关系和捕食关系，扩展域并查集通过将每个动物拆分成多个域来表示其可能的类别（如 A、B、C），从而高效地处理这些关系。

---

核心思想

1. 拆分域：

   • 每个动物 x 拆分成三个域：
     • x：表示动物 x 属于 A 类。
     • x + n：表示动物 x 属于 B 类。
     • x + 2n：表示动物 x 属于 C 类。
   • 这里的 n 是动物的总数，确保每个域的唯一性。

2. 关系表示：

   • 这里我们结合题意 $A->B->C->A$的食物链，进行分析如下：
   • 如果动物 x 和 y 是同类，那么它们的 A、B、C 域分别属于同一集合。因为题目中只有$ABC$三个物种，同类的下一级物种不会互相吃，同类的天敌也不会互相吃，所以合并的时候需要把猎物和天敌一并更新。
   • 如果动物 x 吃 y，那么：
     • x 的 A 域和 y 的 C 域属于同一集合。
     • unity(x, y + 2 * n);//x的同类是y的天敌
     • x 的 B 域和 y 的 A 域属于同一集合。
     • unity(x + n, y);//x的猎物是y的同类
     • x 的 C 域和 y 的 B 域属于同一集合。这里可以在食物链里模拟一下就能理解。
     • unity(x + 2 * n, y + n);//x的天敌是y的猎物

3. 矛盾检测：

   • 如果当前说法与已维护的关系矛盾，则判断为假话。即同类不能与捕食关系共存。

---

具体步骤

1. 初始化

• 初始化并查集，每个域独立成集合。

  for (int i = 1; i <= 3 * n; i++) {p[i] = i;
  }
  

2. 处理说法

• 对于每种说法，检查是否与已维护的关系矛盾：
  • 说法 1：x 和 y 是同类。
    • 检查 x 的 A 域是否与 y 的 B 或 C 域在同一集合。即没有捕食关系
    • 如果没有矛盾，合并 x 和 y 的 A、B、C 域。
  • 说法 2：x 吃 y。
    • 检查 x 的 A 域是否与 y 的 A 或 C 域在同一集合。即没有同类关系或者反向捕食关系。
    • 如果没有矛盾，合并 x 的 A 域与 y 的 B 域，x 的 B 域与 y 的 C 域，x 的 C 域与 y 的 A 域。

3. 假话统计

• 如果说法与已维护的关系矛盾，则统计为假话。

---

代码实现

#include <iostream>
#include <vector>
using namespace std;const int MAXN = 50010;int p[MAXN * 3]; // 扩展域并查集，每个动物拆分为3个域// 查找函数，带路径压缩
int find(int x) {if (p[x] != x) {p[x] = find(p[x]);}return p[x];
}// 合并函数
void merge(int x, int y) {p[find(x)] = find(y);
}int main() {int n, k;cin >> n >> k;// 初始化扩展域并查集for (int i = 1; i <= 3 * n; i++) {p[i] = i;}int ans = 0; // 假话数量while (k--) {int t, x, y;cin >> t >> x >> y;// 越界或自吃，直接判断为假话if (x > n || y > n) {ans++;continue;}if (t == 2 && x == y) {ans++;continue;}if (t == 1) {// x和y是同类if (find(x) == find(y + n) || find(x) == find(y + 2 * n)) {ans++; // 矛盾} else {// 合并x和y的同类域merge(x, y);merge(x + n, y + n);merge(x + 2 * n, y + 2 * n);}} else {// x吃yif (find(x) == find(y) || find(x) == find(y + 2 * n)) {ans++; // 矛盾} else {// 合并x的A域和y的B域，x的B域和y的C域，x的C域和y的A域merge(x, y + n);merge(x + n, y + 2 * n);merge(x + 2 * n, y);}}}cout << ans << endl;return 0;
}

---

示例分析

输入

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

处理过程

1. 说法 1 101 1：101 越界，假话。
2. 说法 2 1 2：1 吃 2，合并 1 的 A 域与 2 的 B 域，1 的 B 域与 2 的 C 域，1 的 C 域与 2 的 A 域。
3. 说法 2 2 3：2 吃 3，合并 2 的 A 域与 3 的 B 域，2 的 B 域与 3 的 C 域，2 的 C 域与 3 的 A 域。
4. 说法 2 3 3：3 吃 3，自吃，假话。
5. 说法 1 1 3：1 和 3 是同类，检查是否矛盾。如果 1 的 A 域与 3 的 B 或 C 域在同一集合，则矛盾。
6. 说法 2 3 1：3 吃 1，检查是否矛盾。如果 3 的 A 域与 1 的 A 或 C 域在同一集合，则矛盾。
7. 说法 1 5 5：5 和 5 是同类，合法。

输出

3

---

总结

扩展域并查集通过拆分域来表示复杂关系，逻辑直观且易于理解。虽然空间开销较大，但在处理复杂关系问题时非常高效。

带权并查集详解

带权并查集是一种在普通并查集的基础上，为每个节点维护一个权值（或关系）的数据结构。通过权值，我们可以表示节点之间的复杂关系（如捕食关系、同类关系等）。在食物链问题中，带权并查集通过权值来表示动物之间的捕食关系，从而高效地判断给定的说法是否为假话。

---

核心思想

思想是没有合并到一起的集合不会产生矛盾。被合并的集合，有相同的集合代表，根据该点和集合代表点的关系推断。

1. 权值定义：

   • 每个节点 x 维护一个权值 d[x]，表示 x 与其父节点 p[x] 的关系。
   • 权值的具体含义：
     • d[x] = 0：x 和 p[x] 是同类。
     • d[x] = 1：x 吃 p[x] 。
     • d[x] = 2：x 被 p[x]吃。

2. 路径压缩：

   • 在查找根节点的过程中，路径压缩会将每个节点的父节点直接指向根节点，并更新权值 d[x]，确保权值表示的是 x 到根节点的总关系。

3. 关系推导：

   • 通过权值的模运算，可以推导出任意两个节点之间的关系。
   • 例如：
     • 如果 d[x] = 1，d[y] = 0，则 x 吃 y 。
     • 如果 d[x] = 2，d[y] = 1，则 x 吃 y 。

4. 合并操作：

   • 当合并两个集合时，根据当前说法调整权值，确保合并后的关系正确。

---

具体步骤

1. 初始化

• 初始化并查集，每个节点的父节点为自身，权值为 0。

  for (int i = 1; i <= n; i++) {p[i] = i;d[i] = 0;
  }
  

2. 查找函数

• 查找节点 x 的根节点，并在路径压缩的过程中更新权值。

  int find(int x) {if (p[x] != x) {int orig_p = p[x]; // 保存原始父节点p[x] = find(p[x]); // 递归找到根节点d[x] = (d[x] + d[orig_p]) % 3; // 更新权值}return p[x];
  }
  

3. 处理说法

• 对于每种说法，检查是否与已维护的关系矛盾：
  • 说法 1：x 和 y 是同类。
    • 找到 x 和 y 的根节点 rx 和 ry。
    • 如果 rx == ry，检查 d[x] 和 d[y] 是否相等。
    • 如果 rx != ry，合并两个集合，并调整权值。
  • 说法 2：x 吃 y。
    • 找到 x 和 y 的根节点 rx 和 ry。
    • 如果 rx == ry，检查 (d[x] - d[y] + 3) % 3 是否等于 1。
    • 如果 rx != ry，合并两个集合，并调整权值。

4. 假话统计

• 如果说法与已维护的关系矛盾，则统计为假话。

---

代码实现

#include <iostream>
#include <vector>
using namespace std;const int MAXN = 50010;int p[MAXN]; // 父节点数组
int d[MAXN]; // 权值数组，表示与父节点的关系// 查找函数，带路径压缩和权值更新
int find(int x) {if (p[x] != x) {int orig_p = p[x]; // 保存原始父节点p[x] = find(p[x]); // 递归找到根节点d[x] = (d[x] + d[orig_p]) % 3; // 更新权值}return p[x];
}int main() {int n, k;cin >> n >> k;// 初始化并查集for (int i = 1; i <= n; i++) {p[i] = i;d[i] = 0;}int ans = 0; // 假话数量while (k--) {int t, x, y;cin >> t >> x >> y;// 越界或自吃，直接判断为假话if (x > n || y > n) {ans++;continue;}if (t == 2 && x == y) {ans++;continue;}int rx = find(x), ry = find(y); // 找到x和y的根节点if (rx != ry) {// 合并两个集合p[rx] = ry;if (t == 1) {d[rx] = (d[y] - d[x] + 3) % 3; // x和y是同类} else {d[rx] = (d[y] - d[x] + 4) % 3; // x吃y}} else {// 同一集合内，检查关系是否矛盾if (t == 1 && (d[x] - d[y] + 3) % 3 != 0) {ans++;} else if (t == 2 && (d[x] - d[y] + 3) % 3 != 1) {ans++;}}}cout << ans << endl;return 0;
}

---

示例分析

输入

100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5

处理过程

1. 说法 1 101 1：101 越界，假话。
2. 说法 2 1 2：1 吃 2，合并 1 和 2 的集合，调整权值。
3. 说法 2 2 3：2 吃 3，合并 2 和 3 的集合，调整权值。
4. 说法 2 3 3：3 吃 3，自吃，假话。
5. 说法 1 1 3：1 和 3 是同类，检查是否矛盾。
6. 说法 2 3 1：3 吃 1，检查是否矛盾。
7. 说法 1 5 5：5 和 5 是同类，合法。

输出

3

---

总结

带权并查集通过维护权值来表示节点之间的关系，路径压缩和权值更新确保了高效的关系推导。虽然逻辑稍复杂，但代码简洁且高效，适合处理类似食物链的问题。