luogu P2024 食物链
2024-10-11 17:27:27
题目描述
动物王国中有三类动物 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
并查集 f【a】表示同一种f【a+n】表示吃f【a+n*2】表示被吃
#include <cstdio>
#include <iostream>
#include <cstring> using namespace std;
const int N = ;
int n,k; int read() {
int x=,f=;
char c=getchar();
while (c < '' || c > ''){if(c=='-')f=-;c=getchar();}
while (c <= ''&&c >= ''){x=x*+c-'';c=getchar();}
return x*f;
} int ans=;
int father[N*];
int find(int x)
{
if(x!=father[x])father[x]=find(father[x]);
return father[x];
}
void unionn(int x,int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
father[fx]=fy;
}
int main()
{
//freopen("eat.in","r",stdin);
//freopen("eat.out","w",stdout);
n=read();k=read();
int a,b,c;
for(int i=;i<=n*;i++)father[i]=i; for(int i=;i<=k;i++)
{
a=read();b=read();c=read();
if(b>n||c>n||b<||c<){ans++;continue;}
if(a==)
{
if(find(b+n)==find(c)||find(b+*n)==find(c)){ans++;continue;}
unionn(b,c);unionn(b+n,c+n);unionn(b+*n,c+*n);
}
else
{
if(find(b)==find(c)||find(b+*n)==find(c)){ans++;continue;}
unionn(b,c+*n);unionn(b+n,c);unionn(b+*n,c+n);
}
} printf("%d\n",ans);
return ;
}
最新文章
- Linux 进程间通讯详解七
- PL/SQL使用技巧
- Hamilton回路的判定与构造
- <;Stackoverflow>; 如何提问
- 静态文件服务器(The static file servers)
- SSAS 实例重命名
- 使用hibernate自动创建Mysql表失败原因
- 报错:System.Data.Entity.Infrastructure.DbUpdateException 更新条目时出错
- 【转】HTML5的语音输入 渐进使用HTML5语言识别, so easy!
- Python 代码实现模糊查询
- 4、记录1----获取hdfs上FileSystem的方法 记录2:正则匹配路径:linux、hdfs
- Noip2011提高组总结
- Kettle之数据抽取、转换、装载
- 管理工具 Kafka Manager
- 使用方便 正则表达式grep,sed,awk(一)
- Dell M102ZD-128 —— 拿XP拯救你
- XMind常用快捷方式汇总
- 持续交付之软件包管理maven篇
- classLoader和Class.forName的区别
- (转)InnoDB与MyISAM引擎区别
热门文章
- [NOIP2009]靶形数独 深搜+枝杈优化
- 解决Vue方法中setTimeout改变变量的值无效
- 如何在数据访问层上提高js的执行效率
- RTL2832U+R820T电视棒windows下安装sdr# 以及搭建ADS-B使用VirtualRadar看飞机的教程
- Codeforces Round #350 (Div. 2) A
- LABVIEW伺服电机测试平台
- kuangbin带你飞 生成树专题 : 次小生成树; 最小树形图;生成树计数
- hrtimer的简单使用 + 原理和实现【转】
- 定制一个支持中英文的简单LaTex模板
- Android系统是一个基于BInder通信的C/S架构