当前位置:网站首页>POJ 1182 :食物链(并查集)[通俗易懂]
POJ 1182 :食物链(并查集)[通俗易懂]
2022-07-07 16:53:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
Time Limit: 1000MS | Memory Limit: 10000K | |
---|---|---|
Total Submissions: 43526 | Accepted: 12679 |
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),输出假话的总数。
Input
第一行是两个整数N和K,以一个空格分隔。
下面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
好吧。。
这篇的确是最具体的。。点击打开链接
看了之后对并查集的了解更加深了。。。
弱菜在此感谢博主。。
还有这道题我用多重输入就错了。。
害我弄了好久。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<sstream>
#include<cmath>
using namespace std;
#define M 100500
int n;
int k;
int d;
int x;
int y;
int p[M];
int r[M];
int ans;
void start()
{
for(int i=1; i<=n; i++)
{
p[i]=i; //初始化并查集
r[i]=0; //初始化时。每一个元素作为一个集合,其元素为1
}
}
int find(int x) //并查集的find
{
if( p[x]==x )
return x;
else
{
int t = p[x];
p[x] = find ( p[x] );
r[x] = (r[x]+r[t])%3;
return p[x];
}
}
void Kruskal(int x, int y, int d)
{
int xx = find(x);
int yy = find(y);
p[yy] = xx;
r[yy] = (r[x]-r[y]+3+(d-1))%3;
}
int main()
{
scanf("%d%d", &n, &k);
start();
ans = 0;
for(int i=1; i<=k; i++)
{
scanf("%d%d%d", &d, &x, &y);
if(x>n || y>n || (d==2&&x==y))
ans++;
else if( find(x) == find(y) )
{
if( d==1 && r[x]!=r[y] )
ans++;
if( d==2 && (r[x]+1)%3 != r[y] )
ans++;
}
else
Kruskal(x, y, d);
}
printf("%d\n", ans);
return 0;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116605.html原文链接:https://javaforall.cn
边栏推荐
- Short selling, overprinting and stock keeping, Oriental selection actually sold 2.66 million books in Tiktok in one month
- Creative changes brought about by the yuan universe
- RISCV64
- 二叉树的基本概念和性质
- pip相关命令
- [Tawang methodology] Tawang 3W consumption strategy - U & a research method
- 低代码助力企业数字化转型会让程序员失业?
- Datasimba launched wechat applet, and datanuza accepted the test of the whole scene| StartDT Hackathon
- Introduction de l'API commune de programmation de socket et mise en œuvre de socket, select, Poll et epoll
- CVPR 2022 - learning non target knowledge for semantic segmentation of small samples
猜你喜欢
Redis
CVPR 2022 - learning non target knowledge for semantic segmentation of small samples
Short selling, overprinting and stock keeping, Oriental selection actually sold 2.66 million books in Tiktok in one month
Basic concepts and properties of binary tree
我感觉被骗了,微信内测 “大小号” 功能,同一手机号可注册两个微信
Some key points in the analysis of spot Silver
Save the memory of the model! Meta & UC Berkeley proposed memvit. The modeling time support is 30 times longer than the existing model, and the calculation amount is only increased by 4.5%
Introduction de l'API commune de programmation de socket et mise en œuvre de socket, select, Poll et epoll
Standard ACL and extended ACL
6.关于jwt
随机推荐
学习open62541 --- [67] 添加自定义Enum并显示名字
如何给“不卖笔”的晨光估值?
行业案例|数字化经营底座助力寿险行业转型
Redis集群与扩展
链式二叉树的基本操作(C语言实现)
[sword finger offer] 59 - I. maximum value of sliding window
Tsinghua, Cambridge and UIC jointly launched the first Chinese fact verification data set: evidence-based, covering many fields such as medical society
Golang client server login
2022年推荐免费在线接收短信平台(国内、国外)
"Decryption" Huawei machine vision Corps: Huawei is moving up and the industry is moving forward
String type, constant type and container type of go language
Hash, bitmap and bloom filter for mass data De duplication
NAT地址转换
[unity shader] insert pass to realize the X-ray perspective effect of model occlusion
Desci: is decentralized science the new trend of Web3.0?
Thread pool and singleton mode and file operation
Cloud security daily 220707: Cisco Expressway series and telepresence video communication server have found remote attack vulnerabilities and need to be upgraded as soon as possible
Learn open62541 -- [67] add custom enum and display name
静态路由配置
DataSimba推出微信小程序,DataNuza接受全场景考验? | StartDT Hackathon