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
刚开始写的代码总是超时,于是就在网上搜到了一个简洁的解法,就是利用并查集,以前完全没有接触过这个概念,感觉理解起来还是有些困难。
并查集是一种典型的树形数据结构,用于处理一些不相交集合的合并和查询问题。
它的主要操作有初始化、查找和合并。
食物链这道题的解题思想是把有关联的动物都放到一个集合中,因为有相同的根节点,且知道两者分别与根节点的关系,所以这两者的关系也就可以确定了,如果不在一个集合中,则需要将两个集合合并。
具体实现步骤如下:
Father[x]表示x的根节点 rank[x]表示x与根节点的关系
初始化:把每个动物都看做一个集合,且每个集合的根节点就是自己,即Father[x]=x
查找根节点:如果father[x]直接是x,则直接返回;否则,x的根节点是father[x]的根节点,递归求解,同时由于father[x]在变,需要修改rank[x]
合并集合:如果a和b不在同一个集合,需要合并,可以将a的根节点的父节点指向b的根节点
#include <stdio.h>
/* father[x]表示x的根节点 */
int father[50005];
/*
rank[x]表示father[x]与x的关系
rank[x] == 0 表示father[x]与x是同类
rank[x] == 1 表示x吃father[x]
rank[x] == 2 表示father[x]吃x
*/
int rank[50005];
/* 初始化集合 */
void Make_Set(int x)
{
father[x] = x;
}
/* 查找x所在的集合 */
int Find_Set(int x)
{
int t;
if (father[x] == x) return x;
t = father[x];
father[x] = Find_Set(father[x]);
/* 因为压缩时根节点改变,必须更新father[x]与x的关系 */
rank[x] = (rank[t] + rank[x]) % 3;
return father[x];
}
/* 合并a和b */
void Union_Set(int a, int b, int len)
{
int ra = Find_Set(a);
int rb = Find_Set(b);
/* 将集合ra合并到集合rb上 */
father[ra] = rb;
/* 更新father[ra]与ra的关系 */
rank[ra] = (rank[b] - rank[a] + 3 + len) % 3 ;
}
int main()
{
int i, n, m;
int d, x, y;
int rx, ry;
int sum = 0;
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
Make_Set(i);
}
while(m--)
{
scanf("%d%d%d", &d, &x, &y);
if (x > n || y > n || (d == 2 && x == y))
{
sum++;
}
else
{
/* 求出x和y所在的集合rx和ry */
rx = Find_Set(x);
ry = Find_Set(y);
/* 若在同一个集合则可确定x和y的关系 */
if (rx == ry)
{
if((rank[x] - rank[y] + 3) % 3 != d - 1)
{
sum++;
}
}
/* 无法确定关系时按照规则合并节点 */
else
{
Union_Set(x, y, d - 1);
}
}
}
printf("%d\n", sum);
return 0;
}
分享到:
相关推荐
poj 食物链代码.带权并查集,关键是找到其中的一些关系式.
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
这份代码用C++实现了经典算法并查集,来源于poj题目1182
poj 1611 The Suspects 代码 并查集的应用
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
并查集基础 acm 算法 poj oi 并查集基础.ppt
POJ1089 并查集可以解决 并查集加路径压缩
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj分类poj分类poj分类poj分类
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
ACM组合数学波利亚计数解析,通过例题解释波利亚计数的简单入门用法。
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
poj 百练 题目分类 poj 百练 题目分类
西北工业大学POJ作业100份源代码. 每个人的poj顺序是不一样的, 不过还是有参考价值的.