食物链

时间：2020-06-18 12:00:14 收藏：0 阅读：50

食物链

Description

动物王国中有三类动物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（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

Input

第一行是两个整数N和K，以一个空格分隔。

以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。

若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

Output

只有一个整数，表示假话的数目。

Sample Input

Sample Output

这道题之前我有记录过用一般并查集的做法：开三倍空间的并查集，显然这个题给的又都是相对关系，不能够确定具体的某个动物属于哪个物种，因此才有开三倍空间来处理的那样的思路，但是带权并查集就是用来处理相对关系的，可以考虑用带权并查集来做。

在这个题中相对关系就是食物链上的关系，因此带权并查集中的权值就应该记录两个动物在食物链上的相对关系，A->B为0表示同类，为1表示A吃B，为2表示A被B吃。这个值不同于前面两个题中的区间合、分数差，它是不可以直接累加的，要考虑三个问题：

路径压缩时，如何更新Value

如果现在有A->B为1，B->C为1，怎么求A->C？显然A吃B，B吃C，那么由题意C应该吃A，那么A->C应该为2；
如果现在有A->B为2，B->C为2，怎么求A->C？显然B吃A，C吃B，那么由题意A应该吃C，那么A->C应该为1；
如果现在有A->B为0，B->C为1，怎么求A->C？显然A、B同类，B吃C，那么由题意A应该吃C，那么A->C应该为1；

找规律不难发现，A->C = (A->B + B->C) % 3，因此关系值的更新需要累加再模3。

区间合并时，如何更新Value

由1不难发现，本题的Value更新无非就是多了个取模操作，因此不难验证区间合并的更新操作应该为：

relationWithParent[fx] = (-relationWithParent[x] + relation + relationWithParent[y]) % 3

3.如何判断是否矛盾

不同于分数、区间和，可以直接相减得到计算结果，这里要解决如果已知A与根节点的关系，B与根节点的关系，如何求A、B之间的关系？由于关系值的计算要模3，因此A->B=(A->C - B->C + 3) % 3，加三是为了避免负数的影响。将A->B与题目给的Relation值判等比较即可。

注意，本题给的relation值都是1或2，在实际处理的时候，这个值应该减1。

#include <bits/stdc++.h> 
using namespace std;
int fa[300001];
//并查集 
int find(int x)//查找 
{
	if(x != fa[x])
	{
		fa[x] = find(fa[x]);
	}
	return fa[x];
}
int unity(int x, int y)//合并 
{
	int r1 = find(fa[x]);
	int r2 = find(fa[y]);
	fa[r1] = r2;
}
int main()
{
	int i, n, k, x, y, z;
	int ans = 0;
	scanf("%d %d", &n, &k);//输入 
	for(i = 1; i <= 3 * n; i++)//初始化 
	{
		fa[i] = i; 
	}
	// x是同类，x + n是猎物， x + 2 * n是天敌 
	for(i = 1; i <= k; i++)
	{
		scanf("%d %d %d", &z, &x, &y);
		if(x > n || y > n)//x和y不能大于n 
		{
			ans++;//假话++ 
		}
		else
		{
			if(z == 1)//x和y是同类 
			{
				if(find(x + n) == find(y) || find(x + 2 * n) == find(y))//如果是同类，x不能是y的猎物或天敌 
				{
					ans++;//假话++ 
				}
				else
				{
					unity(x, y);//x的同类是y的同类 
					unity(x + n, y + n);//x的猎物是y的猎物
					unity(x + 2 * n, y + 2 * n);//x的天敌是y的天敌 
				}
			}
			else//y是x的猎物 
			{
				if(x == y || find(x) == find(y) || find(x + 2 * n) == find(y))//如果y是x的猎物，x不能是y的猎物，x不能和y是同类，y不能是x的天敌 
				{
					ans++;//假话++ 
				}
				else
				{
					unity(x, y + 2 * n);//x的同类是y的天敌 
					unity(x + n, y);//x的猎物是y的同类
					unity(x + 2 * n, y + n);//x的天敌是y的猎物
				}
			}
		}
	}
	printf("%d", ans);//输出 
	return 0;
}

原文：https://www.cnblogs.com/wozuishuaiwozuiniu6/p/13156461.html