Luogu P2024 [NOI2001] food chain

Title Link

Click here ww

 

Title Description

In the animal kingdom, there are three kinds of animals a, B and C. The food chain of these three kinds of animals forms an interesting ring. A eat B, B eat C, C eat a.

There are N animals, numbered 1-N. Every animal is one of a, B and C, but we don't know which one it is.

There are two ways to describe the food chain relationship of these N animals:

The first is "1 X Y", which means that X and Y are the same kind.

The second is "2 X Y", which means X eats Y.

For N animals, he said K sentences one by one in the above two ways, some of which are true and some are false. When a sentence satisfies one of the following three, it is a lie, otherwise it is the truth.

• the current words conflict with some of the real words in front, that is, lies

• in the current conversation, X or Y is larger than N, which is a lie

The current words mean that X eats X, which is a lie

Your task is to output the total number of lies according to the given N and K sentences.

 

Title Solution

I used and looked it up

The idea of anti set is mainly applied

See notes for details.

 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 For itself, x+n For prey x+n*2 Natural enemies
 8 
 9 int find(int k){//lookup
10     if(f[k]==k)
11         return k;
12     return f[k]=find(f[k]);
13 }
14 
15 void unionn(int x,int y){//merge
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++;//Out of scope, lies
32             continue;
33         }
34         if(judge==1){
35             if(find(x+n)==find(y) || find(x+n*2)==find(y)){
36                 ans++;//It can't be the same as natural enemies and prey
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++;//I eat myself
47                 continue;
48             }
49             if(find(x)==find(y) || find(x+n*2)==find(y)){
50                 ans++;//I eat myself && Eat natural enemies
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 }

Tags: C++

Posted on Mon, 06 Jan 2020 23:46:28 -0800 by sumfight