洛谷 P2024 [NOI2001]食物链

2018-08-13 07:35:40来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接

点这里ww

 

题目描述

动物王国中有三类动物 A,B,C,这三类动物的食物链构成了有趣的环形。A 吃 B,B吃 C,C 吃 A。

现有 N 个动物,以 1 - N 编号。每个动物都是 A,B,C 中的一种,但是我们并不知道它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述:

第一种说法是“1 X Y”,表示 X 和 Y 是同类。

第二种说法是“2 X Y”,表示 X 吃 Y 。

此人对 N 个动物,用上述两种说法,一句接一句地说出 K 句话,这 K 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。

? 当前的话与前面的某些真的话冲突,就是假话

? 当前的话中 X 或 Y 比 N 大,就是假话

? 当前的话表示 X 吃 X,就是假话

你的任务是根据给定的 N 和 K 句话,输出假话的总数。

 

题解

这道题我用了并查集求解

主要应用了反集的思想

详见注释

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 const int maxn=50005;
 7 int f[maxn*3],ans=0;//x为本身,x+n为猎物,x+n*2为天敌
 8 
 9 int find(int k){//查找
10     if(f[k]==k)
11         return k;
12     return f[k]=find(f[k]);
13 }
14 
15 void unionn(int x,int y){//合并
16     x=find(x);
17     y=find(y);
18     f[x]=y;
19 }
20 
21 int main(){
22     int n,k;
23     cin>>n>>k;
24     for(int i=1;i<=n*3;i++){
25         f[i]=i; 
26     }
27     for(int i=1;i<=k;i++){
28         int judge,x,y;
29         cin>>judge>>x>>y;
30         if(x>n || y>n){
31             ans++;//在范围之外,是假话
32             continue;
33         }
34         if(judge==1){
35             if(find(x+n)==find(y) || find(x+n*2)==find(y)){
36                 ans++;//本身与天敌与猎物不可能为同类
37                 continue;
38             }
39             unionn(x,y);
40             unionn(x+n,y+n);
41             unionn(x+n*2,y+n*2);
42             continue;
43         }
44         if(judge==2){
45             if(x==y){
46                 ans++;//我吃我自己
47                 continue;
48             }
49             if(find(x)==find(y) || find(x+n*2)==find(y)){
50                 ans++;//我吃我自己 && 吃天敌
51                 continue;
52             }
53             unionn(x+n*2,y+n);
54             unionn(x+n,y);
55             unionn(x,y+n*2);
56             continue;
57         }
58     }
59     cout<<ans;
60     return 0;
61 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:poj_3628 Bookshelf 2

下一篇:Qt动态链接库的创建和使用