P2024 [NOI2001] 食物链

Solution:

使用拓展域并查集，\(1-n\) 表示 \(\rm A\) 群落，\(n+1-2n\) 是 \(\rm B\) 群落，\(2n+1 - 3n\) 是 \(\rm C\) 群落

那么对于操作一，我们首先判断 \(x\) 是否吃了 \(y\) 或 \(y\) 是否吃了 \(x\) .

• 若吃了，那么这句话为假

• 若没吃，则将 (x,y) (x+n,y+n) (x+2n,y+2n) 三条边连上

对于操作二，同理若果 \(x\) 与 \(y\) 是否是同类或 \(y\) 吃了 \(x\)，这句话就为假。

否则就连 (x,y+2n) (x+n,y) (x+2n,y+n) 三条边。

注意判断 \(x\) 与 \(y\) 是否大于 \(n\)

code:

#include<bits/stdc++.h>
#define int long long
#define Flow {ans++;continue;} //假的时候
using namespace std;

const int N=5e4+10;
int f[N*3],n;
int findfa(int x){return f[x]=(f[x]==x)?x:findfa(f[x]);}
int ans;

signed main(){
	std::ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>n>>T;
	for(int i=1;i<=3*n;i++)f[i]=i;
	while(T--){
		int opt,x,y;
		cin>>opt>>x>>y;
		if(x>n||y>n)Flow;//注意这里判断是否越界
		if(opt==1){
			if(findfa(x)==findfa(y+n)||findfa(x+n)==findfa(y))Flow;//判断
			f[findfa(x)]=findfa(y);// 连边
			f[findfa(x+n)]=findfa(y+n);
			f[findfa(x+2*n)]=findfa(y+2*n);
		}
		else{
			if(findfa(x)==findfa(y)||findfa(x)==findfa(y+n))Flow;
			f[findfa(x)]=findfa(y+2*n);
			f[findfa(x+n)]=findfa(y);
			f[findfa(x+2*n)]=findfa(y+n);
		}
	}
	cout<<ans<<endl;
	
	return 0;
}