![洛谷 P2024：[NOI2001] 食物链 ← 扩展域并查集](images/page-header-bg.jpg)
![洛谷 P2024：[NOI2001] 食物链 ← 扩展域并查集](http://pic.xiahunao.cn/yaotu/洛谷 P2024：[NOI2001] 食物链 ← 扩展域并查集)
【题目来源】https://www.luogu.com.cn/problem/P2024【题目描述】动物王国中有三类动物 ABC这三类动物的食物链构成了有趣的环形。A 吃 BB 吃 CC 吃 A。现有 N 个动物以 1∼N 编号。每个动物都是 ABC 中的一种但是我们并不知道它到底是哪一种。有人用两种说法对这 N 个动物所构成的食物链关系进行描述第一种说法是 1 X Y表示 X 和 Y 是同类。第二种说法是 2 X Y表示 X 吃 Y。此人对 N 个动物用上述两种说法一句接一句地说出 K 句话这 K 句话有的是真的有的是假的。当一句话满足下列三条之一时这句话就是假话否则就是真话。1当前的话与前面的某些真的话冲突就是假话2当前的话中 X 或 Y 比 N 大就是假话3当前的话表示 X 吃 X就是假话。你的任务是根据给定的 N 和 K 句话输出假话的总数。【输入格式】第一行两个整数NK表示有 N 个动物K 句话。第二行开始每行一句话。格式见题目描述与样例。【输出格式】一行一个整数表示假话的总数。【输入样例】100 71 101 12 1 22 2 32 3 31 1 32 3 11 5 5【输出样例】3【数据范围】对于全部数据1≤N≤5×10^41≤K≤10^5。∣X∣,∣Y∣2^32。【算法分析】● 基础并查集https://blog.csdn.net/hnjzsyjyj/article/details/146948171int find(int x) { if(x!pre[x]) pre[x]find(pre[x]); return pre[x]; } void merge(int x,int y) { int afind(x); int bfind(y); if(a!b) pre[a]b; } for(int i1; in; i) pre[i]i;● 扩展域并查集https://blog.csdn.net/hnjzsyjyj/article/details/162165317扩展域并查集1扩展域并查集是一种高效处理多关系问题的数据结构通过扩展元素的“逻辑域”来维护复杂关系适用于传统基础并查集无法解决的场景。缺点是需扩展多倍数组空间占用较高。2在扩展域并查集中父数组的大小为 n×k其中 n 是元素总数k 是每个元素的“逻辑域”数。3扩展域并查集中的“逻辑域”数等于给定问题中互斥关系的种类数”。例如在食物链问题中物种间的关系不是简单的“吃”与“被吃”而是循环依赖如 X 吃 Y、Y 吃 Z、Z 吃 X是一个封闭的循环。在这个循环中每个物种有三种可能的“角色”同类域、食物域、天敌域且这三种角色循环轮替。4为什么必须用“域”来表示并查集仅能判断两个元素是否属于同一连通集合只能描述无向等价关系无法表达单向约束。食物链里 “X 吃 Y” 是单向关系直接用原始动物节点无法区分 “X 吃 Y” 和 “Y 吃 X”。因此需要将同一个动物拆出三类逻辑分身同类域、食物域、天敌域代表该动物在不同捕食关系中的身份通过合并不同动物对应域的分身把单向捕食约束转化为无向集合连通关系用集合归属间接存储整套有向逻辑。5由于食物链的底层逻辑是循环依赖如 X 吃 Y、Y 吃 Z、Z 吃 X故针对动物 i用i表示 i 的同类域 、用in表示 i 的食物域、用i2n表示 i 的天敌域。当声明“X 吃 Y”时本质上是在说X 的食物域 Y 的同类域、X 的天敌域 Y 的食物域、X 的同类域 Y 的天敌域。当声明“X 吃 Y”时其关系代码如下所示。merge(x, y2*n); // X 的同类域 Y 的天敌域 merge(xn, y); // X 的食物域 Y 的同类域 merge(x2*n, yn); // X 的天敌域 Y 的食物域【算法代码】#include bits/stdc.h using namespace std; const int N5e45; int pre[N*3]; int find(int x) { if(x!pre[x]) pre[x]find(pre[x]); return pre[x]; } void merge(int x,int y) { int afind(x); int bfind(y); if(a!b) pre[a]b; } int main() { int n,k,ans0; cinnk; for(int i1; i3*n; i) pre[i]i; while(k--) { int op,x,y; cinopxy; if(xn || yn) { ans; continue; } if(op1) { if(find(x)find(yn) || find(x)find(y2*n)) ans; else { merge(x,y); merge(xn,yn); merge(x2*n,y2*n); } } else { if(find(x)find(y) || find(x)find(yn)) ans; else { merge(x,y2*n); merge(xn,y); merge(x2*n,yn); } } } coutans; return 0; } /* in: 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 out: 3 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/162165317https://blog.csdn.net/hnjzsyjyj/article/details/146433179
