【题解】P2024 [NOI2001]食物链 - 数据结构 - 并查集

时间：2021-03-15 20:38:59

P2024 [NOI2001]食物链

声明：本博客所有题解都参照了网络资料或其他博客，仅为博主想加深理解而写，如有疑问欢迎与博主讨论✧｡٩(ˊᗜˋ)و✧*｡

题目描述

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

现有 \(N\) 个动物，以 \(1 － 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\) 句话，输出假话的总数。

Solution

接触并查集已经有好一段时间了，但还是第一次见这种(我太菜了

在同一个并查集中的元素并不一定代表它们是同一种，而是代表它们之间有关系

于是就用一个 \(3\) 倍的并查集来写

设 \(1\ -\ n\) 吃 \(n+1\ -\ 2*n\) ，\(n+1\ -\ 2*n\) 吃 \(2 * n + 1\ -\ 3 * n\) ，\(2 *n + 1\ -\ 3 * n\) 吃 \(1\ -\ n\)

由于只需知道它们之间的关系，而固定是 \(A\ B\ C\) 哪一个集合并不重要，所以在连边时要把三个集合中每个都连起来

\(eg:\ n = 5\) 时，\(2\) 吃 \(3\)，则要把 \(2\) 和 \(3 + 5\) ，\(2 + 5\) 和 \(3 + 2 * 5\) ，\(2 + 2 * 5\) 和 \(3\) 都连起来

这里可以参照这篇博客 , 我觉得有他画的图就很容易理解

Code

#include<iostream>

#include<cstdio>

#include<fstream>

#include<algorithm>

#include<cmath>

#define F(i, x, y) for(int i = x; i <= y; ++ i)

using namespace std;

int read();

const int N = 150000;

int n, k, ans;

int x, y, z;

int s[N];

int search(int x)

{

	int n = x, tmp;

	while(x != s[x]) x = s[x];

	while(n != x) tmp = s[n], s[n] = x, n = tmp;

	return x;

}

int main()

{

	n = read(), k = read();

	F(i, 1, 3 * n) s[i] = i;

	while(k --)

	{

		z = read(), x = read(), y = read();

		if((x == y && z == 2) || x > n || y > n) {++ ans; continue;}

		if(z == 1)

		{

			if(search(x) == search(y + n) || search(x) == search(y + 2 * n)) {++ ans; continue;}

			if(search(x) != search(y))

				s[search(x)] = search(y), s[search(x + n)] = search(y + n), s[search(x + 2 * n)] = search(y + 2 * n);

		}

		if(z == 2)

		{

			if(search(x) == search(y + 2 * n) || search(x) == search(y)) {++ ans; continue;}

			if(search(x) != search(y + n))

				s[search(x)] = search(y + n), s[search(x + n)] = search(y + 2 * n), s[search(x +2 * n)] = search(y);

		}

	}

	printf("%d", ans);

	return 0;

}

int read()

{

	int x = 0;

	char c = getchar();

	while(c < '0' || c > '9') c = getchar();

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x;

}

相关文章