【NOI2001】【Vijos1531】食物链(并查集拓展域)
【摘要】
problem
森林中有3种动物:A吃B,B吃C,C吃A现有 N 个动物(编号1~n),K句话。 1、1 X Y,表示 X 和 Y 是同类。 2、2 X Y,表示 X 吃 Y。一句话是假话当且仅当:...
problem
- 森林中有3种动物:A吃B,B吃C,C吃A
- 现有 N 个动物(编号1~n),K句话。
1、1 X Y,表示 X 和 Y 是同类。
2、2 X Y,表示 X 吃 Y。 - 一句话是假话当且仅当:
1、与前面的冲突。
2、X吃X。
3、编号大于N。 - 判断当前话的真假。
solution
一、考虑补集:
- 把每个动物x拆成三个节点:其中i用来连接与i同类的,i+n用来连接能吃i的,i+2*n用来连接i能吃的。(具体来说,凡是与i+n节点在同一个集合里的,都是被i吃的动物。)
二、考虑合并:
- 对于X和Y是同类:则说明“X的同类”与“Y的同类”一样,“X的捕食”与“Y的捕食”一样,“X的天敌”与“Y的天敌”一样。我们分别合并这三个节点。
- 对于X吃Y这样:说明“X的捕食”就是“Y的同类”,“X的同类”就是“Y的天敌”,又因为是环形,所以“X的天敌”就是“Y的捕食”。
三、考虑真假
- 对于X和Y是同类,当且仅当以下2种时出现矛盾:
1、X吃Y。
2、Y吃X。 - 对于X吃Y,当且仅当以下2种时出现矛盾:
1、X和Y是同类。
2、Y吃X。 - 分别判断对应节点是否在同一集合即可。
codes
#include<iostream>
#include<algorithm>
using namespace std;
int ans = 0;
int fa[50010*3];
void init(int n){ for(int i = 1; i <= n; i++)fa[i]=i; }
int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); }
void merge(int x, int y){ x=find(x);y=find(y);if(x!=y)fa[x]=y;}
int some(int x, int y){ return find(x)==find(y); }
int main(){
int n, m;
cin>>n>>m;
init(n*3);
for(int i = 1; i <= m; i++){
int op, x, y;
cin>>op>>x>>y;
if(x>n||y>n){ans++;continue;}//2)当前的话中X或Y比N大,就是假话
if(op==2&&x==y){ans++;continue;}//3)当前的话表示X吃X,就是假话
if(op==1){
if(some(x,y+n)||some(y,x+n))ans++;//如果x吃y或者y吃x,就不是同类
else{
merge(x,y);//x和y是同类
merge(x+n,y+n);//能吃x和y的也是同类
merge(x+n*2,y+n*2);//x和y能吃的也是同类
}
}else{
if(some(x,y)||some(y,x+n))ans++;//如果x和y是同类或者y吃x
else{
merge(x,y+n);//x和吃y的连起来
merge(x+n,y+n*2);//能吃x的和被y吃的连起来(三种动物之间的关系啊)
merge(x+n*2,y);//x能吃的和y连起来
}
}
}
cout<<ans<<"\n";
return 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。
原文链接:gwj1314.blog.csdn.net/article/details/79684523
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)