注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]食物链  

2015-08-17 22:39:38|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
[好题] 关键字:并查集。找规律。

Link&Limit


        [洛谷2024]  [codevs1074]
        时间限制:1000ms  空间限制:131072kb

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 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
        ? 当前的话与前面的某些真的话冲突,就是假话
        ? 当前的话中 X 或 Y 比 N 大,就是假话
        ? 当前的话表示 X 吃 X,就是假话
        你的任务是根据给定的 N 和 K 句话,输出假话的总数。

Input Format


        第一行两个整数,N,K,表示有 N 个动物,K 句话。
        第二行开始每行一句话(按照题目要求,见样例)

Output Format


        一行,一个整数,表示假话的总数。

Sample Input #1


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 #1


3

Hint


        1 ≤ N ≤ 5 ? 10^4;
        1 ≤ K ≤ 10^5

        用并查集进行推理的一道经典题。设root[x]表示x号动物和哪种动物同类,root[x+n]表示x号动物吃的动物和哪种同类,root[x+2n]表示吃x号动物的动物和哪种同类。
        对于第一种说法,如果root[x+n] != root[y] && root[x+2n] != root[y](x不吃y,也不被y吃)那么这句话是真话,之后要进行root[x] = y; root[x+n] = root[y+n]; root[x+2n] = root[y+2n];(x和y同类,x吃的动物和y吃的动物同类,吃x的动物和吃y的动物同类)的操作。
        对于第二种说法,如果root[x] != root[y] && root[x+2n] != root[y](x与y不同类,且x不被y吃)那么这句话是真话,之后要进行root[x+n] = y; root[x+2n] = root[y+n]; root[y+2n] = x;(x吃y,x被y吃的动物吃,y被x吃)的操作。

#include <stdio.h>
int n,m,ans = 0;
int root[150010];
int findroot(int nod)
{
if(root[nod] != nod) root[nod] = findroot(root[nod]);
return root[nod];
}
int main()
{
int i,a,b,x,y,x1,y1,x2,y2,opt;
scanf("%d%d",&n,&m);
for(i=1;i<=n*3;i++) root[i] = i;
while(m--)
{
scanf("%d%d%d",&opt,&a,&b);
if(a>n||b>n) { ans++; continue;}
x = findroot(a); y = findroot(b);
x1 = findroot(a+n); y1 = findroot(b+n);
x2 = findroot(a+(n<<1)); y2 = findroot(b+(n<<1));
if(opt == 1)
{
if(x!=y1&&x!=y2) { root[x] = y; root[x1] = y1; root[x2] = y2;}
else ans++;
}
else
{
if(x!=y&&x!=y1) { root[x1] = y; root[x2] = y1; root[y2] = x;}
else ans++;
}
}
printf("%d",ans);
return 0;
}

  评论这张
 
阅读(9)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018