双倍经验:P2024 [NOI2001] 食物链
当问题要求维护一些对立的关系时(朋友、敌人),就可以用种类并查集实现。
因为有三种关系所以并查集的数组要开三倍空间,第一倍空间存同类关系,第二倍存捕食关系,第三倍存被捕食关系。
注意:一的猎物的猎物就是一的天敌,其他就可以直接并查集维护即可。
注意这题是多组数据要多测清空。
具体判断可以代码,有详细注释,利于理解:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=50005*3;//三倍点
int n,m;
int fa[N];
//查找
int find(int x){
return fa[x]==x?x:find(fa[x]);
}
//合并
void add(int u,int v){
int x=find(u);
int y=find(v);
fa[x]=y;
}
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
cin>>n>>m;
//初始化
for(int i=1;i<=3*n;i++){//
fa[i]=i;
}
int ans=0;//注意多测
while(m--){
int x,y,s;
cin>>s>>x>>y;
//编号超过n,假话。
if(x>n||y>n){
ans++;
continue;
}
if(s==1){
//成为同类但存在捕食关系,假话。
if(find(x+n)==find(y)||find(y+n)==find(x)){
ans++;
}
else{
add(x,y);//同类
add(x+n,y+n);//天敌之间也是同类
add(x+n+n,y+n+n);//天敌的天敌也是同类
}
}
else{
//捕食存在同类和被捕食关系,假话
if(find(x)==find(y)||find(y+n)==find(x)){
ans++;
}
else{
add(x+n,y);//x捕食y
add(x+n+n,y+n);//天敌的捕食
add(x,y+n+n);//天敌的天敌也存在捕食关系
}
}
}
cout<<ans<<"\n";
}
return 0;
}
标签:食物链,捕食,int,题解,fa,add,天敌,find
From: https://www.cnblogs.com/sadlin/p/18414998