P2024 [NOI2001] 食物链
集合间的关系我们常常考虑用并查集维护，这道题不一样的地方是，还需要考虑吃与被吃的关系，我们考虑使用带边权的并查集。因为其中具有 $A$ 吃 $B$ ，$B$ 吃 $C$ ，$C$ 吃 $A$ 这样的循环关系，考虑用 $\bmod 3 $ 来维护。对于一个动物 x 到根节点的距离 d[x] ，$ d[x] = 0 (\bmod 3) $ 表示 x 与根节点是同一种动物，$d[x] = 1 (\bmod 3)$ 表示 x 吃根节点，$d[x] = 2 (\bmod 3)$ 表示 x 被根节点吃。
对于说法 $1$ ，如果两者已经确定了关系，即 $fa(x) = fa(y)$ ，那么判断他们到根节点的距离是否相同即可；否则，将他们合并，更新 x 的父节点的到 y 根节点的距离 dis[p[x]] = (dis[y] - dis[x]) % mod 3 。
对于说法 $2$ ，如果两者已经确定了关系，即 $fa(x) = fa(y)$ ，那么判断他们到根节点的距离是否是 x 吃 y 的关系即可，即 dis[x] = (dis[y] + 1) % 3 ；否则，更新 x 的父节点的到 y 根节点的距离 dis[p[x]] = (dis[y] - dis[x] + 1) % 3 。
实现时，注意减法运算后需要将其加为正数后取模，否则答案时错误的。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| #include <cstdio>
using namespace std;
const int N = 5e4 + 10;
int n, k, ans, p[N], dis[N];
int fa(int x)
{
if (x != p[x])
{
int px = p[x];
p[x] = fa(p[x]);
dis[x] = (dis[x] + dis[px]) % 3;
}
return p[x];
}
int main()
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
{
p[i] = i;
dis[i] = 0;
}
for (int d, x, y; k; k--)
{
scanf("%d%d%d", &d, &x, &y);
if (x > n || y > n || (x == y && d == 2))
{
ans++;
continue;
}
if (d == 1)
{
if (fa(x) == fa(y))
{
if (dis[x] != dis[y])
ans++;
}
else
{
dis[p[x]] = (dis[y] - dis[x] + 3) % 3;
p[p[x]] = p[y];
}
}
else if (d == 2)
{
if (fa(x) == fa(y))
{
if (dis[x] != (dis[y] + 1) % 3)
ans++;
}
else
{
dis[p[x]] = (dis[y] - dis[x] + 4) % 3;
p[p[x]] = p[y];
}
}
}
printf("%d", ans);
return 0;
}
|