[NOI2001] 食物链
题目描述
动物王国中有三类动物 A , B , C A,B,C A,B,C,这三类动物的食物链构成了有趣的环形。 A A A 吃 B B B, B B B 吃 C C C, C C C 吃 A A A。
现有 N N N 个动物,以 1 ∼ N 1 \sim N 1∼N 编号。每个动物都是 A , B , C A,B,C A,B,C 中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这 N N N 个动物所构成的食物链关系进行描述:
- 第一种说法是
1 X Y
,表示 X X X 和 Y Y Y 是同类。 - 第二种说法是
2 X Y
,表示 X X X 吃 Y Y Y。
此人对 N N N 个动物,用上述两种说法,一句接一句地说出 K K K 句话,这 K K K 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
- 当前的话与前面的某些真的话冲突,就是假话;
- 当前的话中 X X X 或 Y Y Y 比 N N N 大,就是假话;
- 当前的话表示 X X X 吃 X X X,就是假话。
你的任务是根据给定的 N N N 和 K K K 句话,输出假话的总数。
输入格式
第一行两个整数, N , K N,K N,K,表示有 N N N 个动物, K K K 句话。
第二行开始每行一句话(按照题目要求,见样例)
输出格式
一行,一个整数,表示假话的总数。
样例 #1
样例输入 #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 × 1 0 4 1\le N\le 5 \times 10^4 1≤N≤5×104, 1 ≤ K ≤ 1 0 5 1\le K \le 10^5 1≤K≤105。
维护到祖宗节点距离的并查集
#include<bits/stdc++.h> // 包含了大多数标准库
using namespace std;
const int z=1e5+10; // 最大可能的动物数量,按题目要求可以处理的最大数据规模
int fa[z],d[z]; // fa数组用于存储每个动物的父节点,d数组用于存储到父节点的距离
// 并查集中查找函数
int find(int i) {
if(fa[i]!=i) { // 如果当前动物不是自己的父节点
int t=find(fa[i]); // 递归查找父节点的父节点
d[i]+=d[fa[i]]; // 更新当前动物到根节点的距离
fa[i]=t; // 路径压缩,直接将父节点设置为根节点
}
return fa[i]; // 返回当前动物的根节点
}
// 主函数
int main() {
int n,k; // n表示动物的数量,k表示给出的说法的数量
int res=0; // 用来记录假话的数量
cin>>n>>k;
for(int i=1;i<=n;i++)
fa[i]=i; // 初始化每个动物的父节点指向自己
while(k--) {
int m,x,y;
cin>>m>>x>>y; // 读取每个说法的类型和动物的编号
if(x>n||y>n) res++; // 如果x或y超过了动物的数量则为假话
else {
int px=find(x),py=find(y); // 查找x和y的根节点
if(m==1) { // 如果说法是x和y是同类
if(px==py&&(d[x]-d[y])%3!=0) res++; // 如果根节点相同但关系不为同类,记录假话
else if(px!=py) {
fa[px]=py; // 合并两个集合
// 更新x到y的距离,使得x和y之间的关系成立,为同类关系
d[px]=d[y]-d[x];
}
} else { // 如果说法是x吃y
if(px==py&&(d[x]-1-d[y])%3!=0) res++; // 如果根节点相同但关系不为捕食关系,记录假话
else if(px!=py) {
fa[px]=py; // 合并两个集合
// 更新x到y的距离,使得x和y之间的关系成立,为捕食关系
d[px]=d[y]+1-d[x];
}
}
}
}
cout<<res<<endl; // 输出假话的数量
return 0;
}
该代码通过并查集管理动物之间的关系,并在读取每个说法时更新这些关系。如果新的说法与已知的关系冲突,就认为这条说法是假话,并累加到结果中。最后,程序输出假话的总数。