P2024 食物链

admin

https://www.luogu.org/problemnew/show/P2024

题目描述
动物王国中有三类动物 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 句话，输出假话的总数。

输入输出格式
输入格式：
从 eat.in 中输入数据

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

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

输出格式：
输出到 eat.out 中

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

输入输出样例
输入样例#1：
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例#1：
3
说明
1 ≤ N ≤ 5 ∗ 10^4

1 ≤ K ≤ 10^5

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n,m,l=0,fa[201000],x,y,a,all=0;
    
14. int getf(int u)
    
15. {
    
16.         if(u==fa[u]) return u;
    
17.         int f=getf(fa[u]);
    
18.         fa[u]=f;
    
19.         return f;
    
20. }
    
21. void he(int x,int y)
    
22. {
    
23.         int t1=getf(x),t2=getf(y);
    
24.                 if(t1!=t2)
    
25.                         fa[t1]=t2;
    
26. }
    
27. int main()
    
28. {
    
29.         scanf("%d%d",&n,&m);
    
30.         for(int i=1;i<=3*n;i++)
    
31.                 fa[i]=i;
    
32.         while(m--)
    
33.         {
    
34.                 scanf("%d%d%d",&a,&x,&y);
    
35.                 if(x>n||y>n)
    
36.                 {
    
37.                         all++;
    
38.                         continue;
    
39.                 }
    
40.                 if(a==1)
    
41.                 {
    
42.                         if(getf(x)==getf(y+n)||getf(x)==getf(y+n+n))
    
43.                         {
    
44.                                 all++;
    
45.                                 continue;
    
46.                         }
    
47.                         he(x,y);he(x+n,y+n);he(x+n+n,y+n+n);
    
48.                 }
    
49.                 else
    
50.                 {
    
51.                         if(x==y||getf(x)==getf(y)||getf(x)==getf(y+n))
    
52.                         {
    
53.                                 all++;
    
54.                                 continue;
    
55.                         }
    
56.                         he(x+n,y);he(x,y+n+n);he(y+n,x+n+n);
    
57.                 }
    
58.         }
    
59.         printf("%d",all);
    
60.     return 0;
    
61. }

复制代码

zhwang

1. #include<cstdio>
   
2. #include<algorithm>
   
3. #include<vector>
   
4. using namespace std;
   
5. int sum,d,x,y;
   
6. int re[5*10000+100];
   
7. int f[5*10000+100];
   
8. int n,k;
   
9. vector<int> getf(int num)
   
10. {
    
11.         vector<int> t(2);
    
12.         if(f[num]==num)
    
13.         {
    
14.                 t[0]=num;
    
15.                 t[1]=0;
    
16.                 return t;
    
17.         }
    
18.         t=getf(f[num]);
    
19.         f[num]=t[0];
    
20.         re[num]=(t[1]+re[num])%3;
    
21.         t[1]=re[num];
    
22.         return t;
    
23. }
    
24. void merge(int a,int b)
    
25. {
    
26.         vector<int> t1(2);
    
27.         t1=getf(a);
    
28.         vector<int> t2(2);
    
29.         t2=getf(b);
    
30.         if(t1[0]==t2[0])
    
31.         {
    
32.                 if(d==1)
    
33.                 {
    
34.                         if(t1[1]!=t2[1])
    
35.                         {
    
36.                                 sum++;
    
37.                         }
    
38.                 }
    
39.                 else
    
40.                 {
    
41.                         if(d==2)
    
42.                         {
    
43.                                 if((d+t2[1]-1)%3!=t1[1])
    
44.                                 {
    
45.                                         sum++;
    
46.                                 }
    
47.                         }
    
48.                 }
    
49.                 return;
    
50.         }
    
51.         f[t1[0]]=t2[0];
    
52.         re[t1[0]]=(d+2-re[x]+re[y])%3;
    
53. }
    
54. int main()
    
55. {
    
56.         scanf("%d%d",&n,&k);
    
57.         for(int i=1;i<=n;i++)
    
58.         {
    
59.                 f[i]=i;
    
60.                 re[i]=0;
    
61.         }
    
62.         for(int i=1;i<=k;i++)
    
63.         {
    
64.                 scanf("%d%d%d",&d,&x,&y);
    
65.                 if(x>n||y>n)
    
66.                 {
    
67.                         sum++;
    
68.                         continue;
    
69.                 }
    
70.                 else
    
71.                 {
    
72.                         if(d==2&&x==y)
    
73.                         {
    
74.                                 sum++;
    
75.                                 continue;
    
76.                         }
    
77.                         else
    
78.                         {
    
79.                                 merge(x,y);
    
80.                         }
    
81.                 }
    
82.         }
    
83.         printf("%d",sum);
    
84.         return 0;
    
85. }

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. #define FOR(i,a,b) for(register int i=a;i<=b;i++)
   
3. using namespace std;
   
4. const int N=50005;
   
5. int n,m,ans,x,y,z,f[N*3];
   
6. int getf(int x)
   
7. {
   
8.     if(f[x]==x)return x;
   
9.     f[x]=getf(f[x]);
   
10.     return f[x];
    
11. }
    
12. void Merge(int x,int y){f[getf(f[x])]=getf(y);return;}
    
13. int main()
    
14. {
    
15.     cin>>n>>m;
    
16.     FOR(i,1,n+n+n){f[i]=i;}
    
17.     while(m--)
    
18.     {
    
19.         cin>>z>>x>>y;
    
20.         if(x>n || y>n){ans++;continue;}
    
21.         if(z==1)
    
22.         {
    
23.             if(getf(x)==getf(y+n) || getf(x+n)==getf(y))ans++;
    
24.             else{Merge(x,y);Merge(x+n,y+n);Merge(x+n+n,y+n+n);}
    
25.         }
    
26.         else
    
27.         {
    
28.             if(getf(x)==getf(y) || getf(x)==getf(y+n))ans++;
    
29.             else{Merge(x+n,y);Merge(x+n+n,y+n);Merge(x,y+n+n);}
    
30.         }
    
31.     }
    
32.     cout<<ans<<endl;
    
33.     return 0;
    
34. }
    

复制代码

周陈诚

1. #include<iostream>
   
2. using namespace std;
   
3. const int mn=100150;
   
4. int f[3*mn];
   
5. int ans,n,k;
   
6. int getfa(int x)
   
7. {
   
8.     if(x==f[x]) return x;
   
9.         f[x]=getfa(f[x]);
   
10.         return f[x];
    
11. }
    
12. int main()
    
13. {
    
14.         cin>>n>>k;
    
15.         for(int i=1;i<=3*n+5;i++) f[i]=i;
    
16.         while(k--){
    
17.     int a,x,y;
    
18.         cin>>a>>x>>y;
    
19.         if (x>n || y>n) {
    
20.         ans++;continue;}
    
21.         if(a==2){
    
22.         if(getfa(x)==getfa(y)||getfa(x+n+n)==getfa(y)) ans++;
    
23.         else{
    
24.         f[getfa(x+n)]=getfa(y);
    
25.         f[getfa(x+n+n)]=getfa(y+n);
    
26.         f[getfa(x)]=getfa(y+n+n);
    
27.         }
    
28.         }
    
29.         else{
    
30.     if(getfa(x+n)==getfa(y)||getfa(x+n+n)==getfa(y)) ans++;
    
31.         else{
    
32.         f[getfa(x)]=getfa(y);
    
33.         f[getfa(x+n)]=getfa(y+n);
    
34.         f[getfa(x+n+n)]=getfa(y+n+n);
    
35.         }                
    
36.         }
    
37.         }
    
38.         cout<<ans;
    
39.         return 0;
    
40. }

复制代码