首页 > > 程序设计 > C/C++ >

洛谷 P2024 [NOI2001]食物链

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

题目链接

点这里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 }