题解 LuoGu P2024 食物链

作者: MayFlyyh 分类: 并查集 发布时间: 2018-03-31 01:20 ė 6 没有评论

题解 LuoGu 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 句话,输出假话的总数。

输入输出格式

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

第二行开始每行一句话(按照题目要求,见样例)

输出一行,一个整数,表示假话的总数。

经过学习,我们了解 本题有两种并查集解法

扩展域

针对每个点与其他点的关系,分别有
1.同类
2.吃
3.被吃的关系

那我们将它拆成三个域 1.A同类 2.B吃 3.C被吃

针对描述的A B C三个关系 可以构造出这样的关系

如果x与y是同类,那么他们被相同的种类吃,也能够吃相同的种类,同时他们与彼此的同类互为同类

所以将 (xA,yA),(xB,yB),(xC,yC) 分别连为一个集合

如果x吃y 那么x吃y的同类,x被y所吃的物种吃,x与吃y的物种为同类

那解决的问题关键就是怎么快速找到y的同类,以及吃y以及y吃的物种的集合了

…………稍待完善

Code:
“`

<pre><code class="line-numbers"><br />#### 边权集

我们将3种关系分别用0,1,2表示,0表示同类
1,表示吃,2表示被吃(与父亲的关系)

假如我们已经知道了x和y,y和z的关系,那我们就可以
通过简单相加后对3取模得到x与z之间的关系

%%hzh

Code:

“`cpp
#include<bits/stdc++.h>
using namespace std;
int n,k,t,x,y,dad[100010],h[100010],X,Y,ans;
int find(int x){
if(!dad[x])return x;
int X=find(dad[x]);
//h[x]表示x和dad[x]的关系
//h[dad[x]]表示dad[x]和X的关系
//要把h[x]变成x和X的关系
h[x]=(h[x]+h[dad[x]])%3;
return dad[x]=X;
}
int merge(int x,int y,int t){
if(x>n||y>n)return 1;
X=find(x);
t-=h[x];
Y=find(y);
t+=h[y];
t=(t+3)%3;
if(X==Y)return t!=0;
dad[X]=Y;
h[X]=t;
return 0;
}
int main(){
scanf(“%d%d”,&n,&k);
while(k–){
scanf(“%d%d%d”,&t,&x,&y);
ans+=merge(x,y,t-1);
}
printf(“%d\n”,ans);
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/190

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部