食物链题解

先简单说一下题目**n**个动物两个操作**1 x y** 表示x y是同类**2 x y** 表示x吃y现在有k句话假话以下条件否则就是真话1. 与真话冲突是假话2. x吃x是假话3. x或者y 大于动物总编号n思路这不是普通的并查集所以我们先回顾一个普通的并查集包括“并”和“查”(1)“并”的思想就是 亲戚的亲戚就是也是亲戚将他们划入一个集合中(2)“查”的思想就是 查看是否根节点相同相同说明在一个集合内否之不在这道题目 不是简单地划入集合中元素与元素之间存在关系1x和y是同类2x吃y3x被y吃所以当我们划入集合地同时重点要另外存他们之间的关系用dist[x]这里重点解释一下什么是dist[x]含义dist[x]: x与x父节点之间的关系(1) 0时 表示同类关系(2) 1时表示x是吃x的父节点的关系(3) 2时表示x是被x的父节点吃的关系对比普通并查集代码实现上的不同**一find()中**找出父节点之后还需要更新一下dist[x],因为我们最终是把两个结点划入一个集合中和同一个根节点进行比较意思就是说我知道x和根节点的关系也知道y和根节点的关系自然就知道x和y之间的关系。所以我们更新dist使得x始终是和他的根节点进行比较。**二在合并时候的不同**在普通并查集中我们对于两个点知道他们是亲戚即把他们之间的根节点统一而带权并查集就是在连接的同时将他们之间的关系也连起来比如说这道食物链的题给定了操作op1是他们之间的关系是同类那么对他们的dist进行操作op2也是一样的道理这个待会仔细讲一下在代码注释里面#includebits/stdc.h using namespace std; const int N 5e46; int fa[N]; //存集合 int dist[N];//存关系 0时同类 1时吃 2时被吃 int find(int x) { int t fa[x];//父节点 if(fa[x]!x) { fa[x]find(fa[x]);//fa[x]递归找根节点 dist[x](dist[x]dist[t])%3;//主要是利用向量来理解等式右边的dist[x]表示x-t, //dist[t]表示的是t-x的根节点这样相加之后表示 //x-根节点这里再重复一下是为了之后判断 //因为比较使用根节点作为媒介的 } return fa[x]; } int main() { int n,k; cinnk; int ans0; for(int i1;in;i) { fa[i]i; dist[i]0;//初始化为0x和x本身就是同类 } while(k--) { int op,x,y; cinopxy; if(xn || yn)//假话 1 { ans; continue; } if(op2 xy)//假话2 { ans; continue; } //是否矛盾假话3 int fx find(x); int fy find(y); if(fxfy)//如果在已经连接好了就看他们之间的关系 { if(op1)//如果是操作是同类的话那他们不是同类关系就是假话 { if((dist[x]-dist[y]3)%3!0) //还是利用向量来理解 //这里就是上文说的好判断利用同一个根节点 //dist[x]为x-根节点dist[y]为y-根节点 //x-y就是dist[x]-dist[y],利用向量来理解 //提醒一下3是为了避免出现负数mod3因为关系是循环 ans; } if(op2)//如果是吃的关系那么如果不是吃就是假话 { if((dist[x]-dist[y]3)%3!1) ans; } } //合并 如果他们之间还没有联系 else{ fa[fx]fy;//将fy和fx合并 fx表示x的根节点fy为y的 if(op1)//是同类的关系。 //现在已知x和fx的关系y和fyfind里面求得的也知道x和y的关系同类op1给的 //那还要将fx和fy的关系联系起来即用dist[fx]表示不然就是散的 //关系式可为fx-x , x-y, y-fy 那么dist[fx](-dist[x]0dist[y]3)%3 { dist[fx] (dist[y]-dist[x]3)%3; } else{ //同理可得 dist[fx] (dist[y]-dist[x]13)%3; } } } coutans;//最后输出结果 return 0; }