[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\)。
题解
思路分析
题目中涉及到需要快速得出ABC三类之间的关系，那么明显可以考虑并查集。
【方法1】带权并查集
d[u] 表示 x 与其对应根节点 root 的关系，0 表示同类，1 表示吃，2 表示被吃。
int find(int u) {
if (u != p[u]) {
int fa = p[u];
p[u] = find(p[u]);
d[u] = (d[u] + d[fa]) % 3;
}
return p[u];
}
// (x,y) 同类合并
int a = find(x), b=find(y);
d[x] + d[a] = d[y]. --> d[a] = (d[y] - d[x] + 3) % 3;
// (x eat y) 合并
d[x] + d[a] = d[y] + 1. --> d[a] = (d[y] - d[x] + 4) % 3;
【方法1】扩展域并查集
将 p[] 数组扩展为原数组的 3 倍，p[1~n] 为 A 类，p[n+1~n2] 为 B 类，p[n2+1~n*3] 为 C 类。
也就是说 (u eat u+n), (u+n eat u+n2) , (u+n2 eat u)
// (x,y) 同类合并
p[find(x)] = find(y);
p[find(x + n)] = find(y + n);
p[find(x + n * 2)] = find(y + n * 2);
// (x eat y) 合并
p[find(x)] = find(y + n * 2);
p[find(x + n)] = find(y);
p[find(x + n * 2)] = find(y + n);
程序实现
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10, INF = 0x3f3f3f3f;
int n, k, p[N * 3], d[N * 3];
int find(int u) {
if (u != p[u]) {
int fa = p[u];
p[u] = find(p[u]);
d[u] = (d[u] + d[fa]) % 3;
}
return p[u];
}
// 带权并查集
int solve1() {
int op, x, y, ans = 0;
cin >> n >> k;
for (int i = 0; i <= n; i++) p[i] = i, d[i] = 0;
while (k--) {
cin >> op >> x >> y;
if (x > n || y > n) { ans++; continue; }
int a = find(x), b = find(y);
if (op == 1) { // x-y 同类
if (a == b && (d[x] - d[y] + 3) % 3) ans++;
if (a != b) {
p[a] = b;
d[a] = (d[y] - d[x] + 3) % 3;
}
} else { // x eat y
if (a == b && (d[x] - d[y] + 3) % 3 != 1) ans++;
if (a != b) {
p[a] = b;
d[a] = (d[y] - d[x] + 4) % 3;
}
}
}
cout << ans << endl;
return 0;
}
// 扩展域并查集
int solve2() {
int op, x, y, ans = 0;
cin >> n >> k;
for (int i = 0; i <= n * 3; i++) p[i] = i;
while (k--) {
cin >> op >> x >> y;
if (x > n || y > n) { ans++; continue; }
if (op == 1) { // x-y 同类
if (find(x) == find(y + n) || find(y) == find(x + n)) {
ans++; continue;
}
p[find(x)] = find(y);
p[find(x + n)] = find(y + n);
p[find(x + n * 2)] = find(y + n * 2);
} else { // X eat y (x 吃 x+n)
if (find(x) == find(y) || find(x) == find(y + n)) {
ans++; continue;
}
p[find(x)] = find(y + n * 2);
p[find(x + n)] = find(y);
p[find(x + n * 2)] = find(y + n);
}
}
cout << ans << endl;
return 0;
}
int main() {
solve1();
// solve2();
}