题意：
动物王国中有三类动物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），输出假话的总数。
思路
对于每只动物i创建三个元素i-A,i-B,i-C,并用这3*N个元素建立并查集。并查集的维护如下：
1.i-x表示"i属于种类x"
2.并查集里的每一个组表示组内所有元素代表的情况都同时发生或不发生
例如：如果i-A和j-B在一个组里，就表示如果i属于种类A那么j一定属于种类B，如果j属于种类B那么i一定属于种类A。
所以，对于并查集的维护，只需要按照下面的操作就可以了
第一种：x和y属于同一种类，合并x-A和y-A x-B和y-B x-C和y-C
第二种：x吃y 合并x-A和y-B，x-B和y-C，x-C和y-A
不过在合并之前，需要先判断合并是否会产生矛盾。例如在第一种信息的情况下，需要检查比如x-A和y-B或者y-C是否在同一组
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<map> #include<vector> #include<set> #include<map> #include<algorithm> #define INF 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' using namespace std; typedef long long ll; const int maxn = 5e4 + 10; int n, k; int f[3 * maxn];//开三倍空间 void init() { for (int i = 0;i <= (n + 1) * 3;++i) { f[i] = i; } } int get_father(int x) { return x == f[x] ? x : f[x] = get_father(f[x]); } void unite(int a, int b) { f[get_father(a)] = get_father(b); } int main() { scanf("%d%d", &n, &k); int ans = 0; init(); for (int i = 1;i <= k;++i) { int flag, x, y; scanf("%d%d%d", &flag, &x, &y); if (x <1 || x > n || y < 1 || y > n) {//如果编号不是1-n ++ans ++ans; continue; } if (flag == 1) {//如果x和y同种类 if (get_father(x) == get_father(y + n) || get_father(x) == get_father(y + 2 * n)) {//判断x和y之间是否有捕食关系 ++ans; } else {//否则的话就把三种可能的情况都合并 unite(x, y); unite(x + n, y + n); unite(x + 2 * n, y + 2 * n); } } else {//如果flag == 2 即存在捕食关系 //判断x和y是否是相等的（即判断是否是x捕食自己的情况） //判断y是否捕食x if (get_father(x) == get_father(y) || get_father(x) == get_father(y + 2 * n))++ans; //否则合并可能的三种捕食关系 else { unite(x, y + n); unite(x + n, y + n * 2); unite(x + 2 * n, y); } } } printf("%d\n", ans); return 0; }
![【洛谷】【动态规划】P1002 [NOIP2002 普及组] 过河卒](https://ucc.alicdn.com/pic/developer-ecology/e0a754f7c32249babcf70d5468e5d7b8.png?x-oss-process=image/resize,h_160,m_lfit)