240. 食物链
- 题目
动物王国中有三类动物 A,B,C𝐴,𝐵,𝐶,这三类动物的食物链构成了有趣的环形。
A𝐴 吃 B𝐵,B𝐵 吃 C𝐶,C𝐶 吃 A𝐴。
现有 N𝑁 个动物,以 1∼N1∼𝑁 编号。
每个动物都是 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𝐾,以一个空格分隔。
以下 K𝐾 行每行是三个正整数 D,X,Y𝐷,𝑋,𝑌,两数之间用一个空格隔开,其中 D𝐷 表示说法的种类。
若 D=1𝐷=1,则表示 X𝑋 和 Y𝑌 是同类。
若 D=2𝐷=2,则表示 X𝑋 吃 Y𝑌。
输出格式
只有一个整数,表示假话的数目。
数据范围
思路:
对于在同一颗树中的节点,根据节点和根节点之间的距离,在树内判断节点之间的关系。
对于不在同一个树内的节点,因为两个树当前没有相连,则代表两个树内的节点是没有任何关系的,则一定是真话,然后将两个树更新成一个大的树即可。
那么,是假话的可能有:
1.超过n
2.在同一个树里面,不满足对于规律(对于x吃x的情况,可以合并到其中)
本题要注意的点:
1.如何判断同一个树内的节点的关系,若x和y,(d[x]-d[y])%3=0,同类;=1(x吃y),=2(y吃x)
2.如何合并两个树:默认x的树合到y的树里。如果是x和y同类的情况,则此时x原本的跟px,要更新其到跟的距离,距离应该满足d[x]-d[y]+d[px]=0,则d[px]=d[y]-d[x]。对于捕食关系类似。
3.对于查找当前树的跟,同时更新点x到跟的距离:首先先跟新其父节点到跟的距离,然后d[x]+=d[p[x]],p[x]是x原本的父节点。
#include<iostream> #include<cstring> using namespace std; const int N=; int ph[N],dis[N]; int n,k; int find(int x) { if(x!=ph[x]) { int t=find(ph[x]);//此处必须先求出ph[x]那个点到跟的距离,放到dis[ph[x]]中,才能去求dis[x],先后顺序要注意。 dis[x]+=dis[ph[x]]; ph[x]=t; } return ph[x]; } int main() { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) ph[i]=i; int ans=0; while(k--) { int d,x,y; scanf("%d%d%d",&d,&x,&y); if(x>n||y>n) { ans++; } else { if(d==1) { int px=find(x),py=find(y); if(px==py && (dis[x]-dis[y])%3)ans++; else if(px!=py) { ph[px]=py; dis[px]=dis[y]-dis[x]; } } else { int px=find(x),py=find(y); if(px==py && (dis[x]-dis[y]-1)%3)ans++; else if(px!=py) { ph[px]=py; dis[px]=dis[y]-dis[x]+1; } } } } printf("%d\n",ans); return 0; }
今天的文章
算法(食物链)分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/bian-cheng-ji-chu/99401.html