食物链 POJ 1182(种类并查集)
2024-08-20 22:41:49
Description
动物王国中有三类动物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句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是"1 X Y",表示X和Y是同类。
第二种说法是"2 X Y",表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。
Input
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
Output
只有一个整数,表示假话的数目。
Sample Input
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
Sample Output
3
解题思路:这道题要我们得出假话的数目,如果这就话和之前的话冲突就是假话。我开始没有什么思路,看了看样例,随手画出了图,感觉像是图论的东西,但其实再仔细想想,其实这是一种状态的划分!!!比如说a和b是同类关系,那就把a和b划分到一个集合中,之后再说a和b是捕食关系一定是假话了。但是这道题的问题在于某一个动物在食物链中的角色不是一定的,一个物种可能作为捕食者也可能是被捕食者,还有可能给出同类之间的关系,那该怎么办呢?将所扮演的三种状态全都表示出来。列如,对于物种x,x代表A类,x+n代表B类,x+2n代表c类,其中A吃B,B吃C,C吃A。
对于两个动物如果是同类关系,那么一定不存在捕食和被捕食关系;如果存在捕食关系,那么一定不存在被捕食和同类关系。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX 50010*3
using namespace std;
int pre[MAX];
int Find(int x)
{
int a;
a=x;
while(pre[a]!=a)
{
a=pre[a];
}
return a;
}
void Union(int root1,int root2)
{
int x,y;
x=Find(root1);
y=Find(root2);
if(x!=y)
{
pre[x]=y;
}
}
int Same(int x,int y)///判断两个物种是否有关系
{
return Find(x)==Find(y);
}
int main()
{
int n,m,i,counts;
int a,b,q;
scanf("%d%d",&n,&m);
counts=;
for(i=;i<=n*;i++)///开三倍的数组
{
pre[i]=i;
}
for(i=;i<=m;i++)
{
scanf("%d%d%d",&q,&a,&b);
if(a<||a>n||b<||b>n)///输入的数不合法为假话
{
counts++;
continue;
}
if(q==)
{
if(Same(a,b+n)||Same(a,b+*n))///存在捕食关系或者被捕食关系
{
counts++;
}
else///建立同类关系
{
Union(a,b);
Union(a+n,b+n);
Union(a+*n,b+*n);
}
}
else if(q==)
{
if(Same(a,b)||Same(a,b+*n))///存在同类或者被捕食关系
{
counts++;
}
else///建立所有的捕食关系
{
Union(a,b+n);
Union(a+n,b+*n);
Union(a+*n,b);
}
}
}
printf("%d\n",counts);
return ;
}
最新文章
- &;#65279导致页面顶部空白一行解决方法 【】
- RelativeLayout布局
- fasta文件拆分与合并
- 高大上技术之sql解析
- The Python web services developer: XML-RPC for Python
- 一天一个mysql函数(二) FIND_IN_SET()
- mysqlsla慢查询分析工具教程
- 大用处--PowerShell Management Library for Hyper-V.
- 前端--关于CSS文本
- 自写的LastPos,寻找字符串里的最后一个字符,RTL里没有提供这个函数——Delphi的String下标是从1开始的
- 在LINUX的命令提示符及CMD命令提示符中显示时间
- Effective JavaScript :第三章
- c++文件读取(一)---输入类使用和查找当前程序路径
- 身为运维的你,怎么掌握python才不会失业
- linux nginx搭配https
- Git版本控制:Git冲突解决 相关错误总结
- [PHP] 适配器模式的日常使用
- redis集群搭建及设置账户(转)
- 开车旅行 [NOIP 2012]
- Django App(六) Customing Admin Form
热门文章
- RandomAccessFile类——高效快捷地读写文件
- com.alibaba.druid检测排查数据库连接数不释放定位代码
- vue数组赋值
- VUE 采坑之旅-- Mint-ui 按需引入报出Module build failed: Error: Couldn&#39;t find preset ";es2015"; relative to directory ";C:\\phpStudy\\PHPTutorial\\WWW\\text\\vuep\\vue-demo";
- PHP 变量分页标签页面源代码技术分享
- 树莓派3B+简单入门
- VS.NET2013发布网站的时候去掉.cs文件(预编译)(转)
- 20155334 实验五 Java网络编程及安全
- WPF中。。DataGrid 实现时间控件和下拉框控件
- PhoneGap3.2安装步骤