[是题解哦] 洛谷 P2024 [NOI2001]食物链

题目链接

点这里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 句话，输出假话的总数。

输入输出格式

输入格式：

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话（按照题目要求，见样例）

输出格式：

输出到 eat.out 中

一行，一个整数，表示假话的总数。

说明

1 ≤ N ≤ 5 ∗ 10⁴

1 ≤ K ≤ 10⁵

题解

这道题我用了并查集求解

主要应用了反集的思想

详见注释

 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 }