P2024 [NOI2001] 食物链(种类+ 拓展域并查集)

发布于 2022-06-21  439 次阅读


题目链接:P2024 [NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路

这道题我们不仅需要维护同类,还需要维护吃与被吃的关系,可以想到用拓展域并查集的思路。

这道题一共有3个五种A、B、C,一共N个动物所以我们要开3 * N的空间。

这里我们将这3N空间划分为3个部分,[1, N]表示物种A,[N + 1, 2 * N]表示物种B、[2 * N + 1, 3 * N]表示物种C。(未必一定是ABC,这里只是表示一个吃与被吃的关系。)

每新增一个关系,需要合并三对点(连接三条边)。

比如新增1 吃 2,那么就要将(1 -> N + 2), (N + 1 -> 2 * N + 2), (2 * N + 1 -> 2)这三条边分别连接起来。如图所示

最后查询1 和 2的关系只需要查询1和2、N+1和2*N+2、2*N+1和2的关系就可以了。

代码

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e4 + 10;
int pre[maxn * 3], N, K;
int root(int x){return pre[x] == x ? x : pre[x] = root(pre[x]);}

int relation(int x,int y)
{
	//1 -> x 与 y同类 
	//2 -> x 吃 y
	//3 -> y 吃 x
	//0 -> 关系未知 
	if(root(x) == root(y))return 1;
	else if(root(x) == root(N + y))return 2;
	else if(root(y) == root(N + x))return 3;
	return 0;
}

signed main()
{
	scanf("%lld %lld", &N, &K);
	for(int i = 1;i <= 3 * N; ++ i)pre[i] = i;
	int ans = 0;
	while(K --)
	{
		int op, x, y;scanf("%lld", &op);
		if(op == 1)
		{
			scanf("%lld %lld", &x, &y);
			//判断关系 
			if(x > N || y > N)ans ++;//先判断一下x y是否合法 
			else if(relation(x, y) == 0)//关系未知,真话、建立关系 
			{
				pre[root(x + N * 0)] = root(y + N * 0);
				pre[root(x + N * 1)] = root(y + N * 1);
				pre[root(x + N * 2)] = root(y + N * 2);
			}else if(relation(x, y) != 1)ans ++;//假话 
		}else if(op == 2)
		{
			scanf("%lld %lld", &x, &y);
			if(x > N || y > N || x == y)ans ++;//先判断一下x y是否合法 
			else if(relation(x, y) == 0)//关系未知,真话、建立关系 
			{
				pre[root(x + N * 0)] = root(y + N * 1);
				pre[root(x + N * 1)] = root(y + N * 2);
				pre[root(x + N * 2)] = root(y + N * 0);
			}else if(relation(x, y) != 2)ans ++;//假话
		}
	}
	printf("%lld\n", ans);
	return 0;
}