本文主要是介绍(Luogu) P2024 [NOI2001]食物链 (并查集)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门
解题思路：将并查集分为三个部分 分别是同类，猎物 ，天敌，取x(x属于1~n)举个栗子，与x一块的为x的同类，与x+n为一块的为x的猎物，与x+2*n为一块的为x的天敌。我们只需要同时维护这三个部分，并用来判断假话即可。由于只有A，B，C三种动物，那么A猎物的猎物就是A的天敌这需要注意维护。代码如下：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f;
const int maxn=5e4+5;
int fa[maxn*3],rk[maxn*3]; //一部分代表同类， 二猎物 ，三天敌
int n,k,ans=0;
void init(){for(int i=0;i<maxn*3;++i)fa[i]=i,rk[i]=1;
}
int find(int x){if(x==fa[x]) return fa[x];else return fa[x]=find(fa[x]);
}
bool ck(int x,int y){x=find(x),y=find(y);if(x==y) return true;else return false;
}
void unite(int x,int y){x=find(x),y=find(y);if(rk[x]<rk[y]) fa[x]=y;else{if(rk[x]==rk[y]) rk[x]++;fa[y]=x;}
}int main(){std::ios::sync_with_stdio(0);init();cin>>n>>k;int x,y,z;for(int i=1;i<=k;++i){cin>>z>>x>>y;if(x>n || y>n){ans++;continue;}if(z==1){ //同类 if(find(x+n)==find(y) || find(x+2*n)==find(y) ){//y是x的猎物 或者 y是x的天敌 即为假话ans++;continue;} unite(x,y),unite(x+n,y+n),unite(x+2*n,y+2*n);//x的同类也是y的同类合并，猎物和天敌同理}else if(z==2){ //x吃y if(find(x)==find(y) || find(x)==find(y+n)){//x与y是同类 或者 y的猎物有xans++;continue;}unite(x+n,y),unite(x,y+2*n),unite(x+2*n,y+n);//x的猎物与y是同类 x的同类是y的天敌 x的天敌是y的猎物 } }cout<<ans<<endl;return 0;
}
这篇关于(Luogu) P2024 [NOI2001]食物链 (并查集)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
