【NOI 2001】食物链（种类并查集）

传送门

Solution:

并查集，维护种类。

father维护可追溯的根节点，num维护与根节点的关系，我们定义0表示x与根节点同类，1表示x吃根节点，2表示根节点吃x。

当getfather(X)==(Y)

若D==1，而num[X]!=num[Y]， 则此话为假。（D==1 表示X与Y为同类，而从num[X]!=num[Y]可以推出 X 与 Y 不同类.矛盾.）

若D==2

当num[X]=num[Y] 矛盾 则此话为假

此外

当num[X]=0&&num[Y]=2是对的 当num[X]=1&&num[Y]=0是对的 当num[X]=2&&num[Y]=1是对的

这三句话 稍加观察就会发现num[X]=(num[Y]+1)%3;

当getfather(X)!=getfather(Y)

此时考虑更新 自己分析一下吧 不想写了qwq

Summarize:

对于这类种类并查集，我们需要分类仔细讨论，归纳出更一般的判断方法。

#include<iostream> #include<cstdio> #define N 50005 using namespace std; int n,k,father[N],num[N],ans;//0->x和y同类 1->x吃y 2->y吃x(y代表x的祖先) int getfather(int x) { if(father[x]==x) return x; int fa=father[x]; father[x]=getfather(father[x]); num[x]=(num[fa]+num[x])%3; return father[x]; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>k; for(int i=1;i<=n;i++) { father[i]=i; num[i]=0; } for(int i=1;i<=k;i++) { int d,x,y; cin>>d>>x>>y; if(x>n||y>n) { ans++; continue; } if(d==2&&x==y) { ans++; continue; } int ax=getfather(x); int bx=getfather(y); if(d==1) { if(ax==bx&&num[x]!=num[y]) { ans++; continue; } else if(ax!=bx) { father[ax]=bx; num[ax]=(3+num[y]-num[x])%3; } } if(d==2) { if(ax==bx) { if(!(num[x]==(num[y]+1)%3)){ ans++; continue; } } else { father[ax]=bx; num[ax]=(3+num[y]-num[x]+1)%3; } } } cout<<ans; return 0; }

转载于:https://www.cnblogs.com/Patrickpwq/articles/9395173.html