poj-1182-食物链【带权并查集】题解

布满荆棘的人生 2021-08-30 00:07 358阅读 0赞

### 目录 ###

*   *   *  1.题目
         *  2.题意
         *  3.思路
         *  4.代码

### 1.题目 ###

动物王国中有三类动物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句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。  
1） 当前的话与前面的某些真的话冲突，就是假话；  
2） 当前的话中X或Y比N大，就是假话；  
3） 当前的话表示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**  
100 7  
1 101 1  
2 1 2  
2 2 3  
2 3 3  
1 1 3  
2 3 1  
1 5 5  
S**ample Output**  
3

### 2.题意 ###

给定K个动物x和y的相对关系，求出里面有多少个错误。

### 3.思路 ###

**带权并查集**，并查集中的权值记录两个动物在食物链上的相对关系，A->B为0表示同类，为1表示A吃B，为2表示A被B吃。  
主要考虑三个问题：  
**1.路径压缩时，更新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。  
**2.区间合并时，如何更新Value**  
由1不难发现，本题的Value更新无非就是多了个取模操作，因此不难验证区间合并的更新操作应该为：  
rlationWithParent\[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。**  
因为我们命令为0表示同类，为1表示A吃B，为2表示A被B吃。而题目中为1表示同类，为2表示A吃B，因此relation-1就与我们给定的关系相对应。

### 4.代码 ###

#define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <stdio.h>
    using namespace std;
    const int maxN = 5e4+10;
    int parent[maxN];
    int relation[maxN];    // 0 ： 同类 1：吃 2：被吃
    /// A吃B B吃C ==> A被C吃 Relation(a,c) = Relation(a,b)+Relation(b,c)
    /// A被B吃 B被C吃 ==> A吃C Relation(a,c) = (Relation(a,b)+Relation(b,c))%3
    int find(int x)
    { 
    	if (x != parent[x])
    	{ 
    		int t = parent[x];
    		parent[x] = find(parent[x]);
    		relation[x] = (relation[x] + relation[t]) % 3;
    	}
    	return parent[x];
    }
    int main()
    { 
    	int n, k;
    	cin >> n >> k;
    	int ans = 0;
    	for (int i = 1; i <= n; i++)
    	{ 
    		parent[i] = i;
    	}
    	while (k--)
    	{ 
    		int rela, x, y;
    		scanf("%d%d%d", &rela, &x, &y);
    		if (x > n || y > n || (rela == 2 && x == y))
    		{ 
    			ans++;
    		}
    		else 
    		{ 
    			int fx = find(x);
    			int fy = find(y);
    			if (fx == fy)
    			{ 
    				if ((rela - 1) != ((relation[x] - relation[y] + 3) % 3))
    					ans++;
    			}
    			else 
    			{ 
    				parent[fx] = fy;
    				relation[fx] = (-relation[x] + rela - 1 + relation[y]) % 3;
    			}
    		}
    	}
    	cout << ans;
    	return 0;
    }

搬运的大佬博客。原文链接: [带权并查集][Link 1].  
这篇博客对带权并查集讲的十分详细，通俗易懂，大家如果还是不懂，可以去看看。

[Link 1]: https://blog.csdn.net/yjr3426619/article/details/82315133