【NOI2001】食物链

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

HINT

输入文件

对7句话的分析 100 7

1 101 1  假话

2 1 2    真话

2 2 3    真话

2 3 3    假话

1 1 3    假话

2 3 1    真话

1 5 5    真话

题解

http://blog.csdn.net/c0de4fun/article/details/7318642

Part I - 权值(relation)的确定。
森林中有3种动物。A吃B,B吃C,C吃A。
以动物之间的关系来作为并查集每个节点的权值。
注意,我们不知道所给的动物所属的种类。
所以,我们可以用动物之间“相对”的关系来确定一个并查集。
0 - 这个节点与它的父节点是同类
1 - 这个节点被它的父节点吃
2 - 这个节点吃它的父节点。

注意,这个0,1,2所代表的意义不是随便制定的,我们看题目中的要求。
第一个数字(下文中,设为d)指定了后面两种动物的关系:
1 - X与Y同类
2 - X吃Y

我们注意到,当 d = 1的时候,( d - 1 ) = 0
当 d = 2的时候,( d - 1 ) = 1,代表Y被X吃
所以,这个0,1,2不是随便选的

Part II - 路径压缩,以及节点间关系确定
我们把所有的动物全初始化。

int relation; //该node与父节点的关系,0同类,1被父节点吃,2吃父节点

初始化
For i = 0 to N do
  ani[i].parent = i;
  ani[i].relation = 0 ; //自己和自己是同类
End For

(1)路径压缩时的节点算法

SET1 = {1,2},我们规定集合中第一个元素为并查集的“代表”
假如现在有语句:
2 2 6
这是一句真话
2是6的父亲
ani[6].parent = 2;
ani[6].relation = 1;
那么,6和1的关系如何呢?
ani[2].parent = 1;
ani[2].relation = 0;
我们可以发现6与2的关系是 1.
ani[now].parent = ani[ani[now].parent].parent;
ani[now].relation = ( ani[now].relation + ani[now.parent].relation ) % 3;
这个路径压缩算法是正确的
注意,根据当前节点的relation和当前节点父节点的relation推出当前节点与其父节点的父节点的relation这个公式十分重要!!
( 儿子relation + 父亲relation ) % 3 = 儿子对爷爷的relation
这就是路径压缩的节点算法

(2) 集合间关系的确定
在初始化的时候,我们看到,每个集合都是一个元素,就是他本身。
这时候,每个集合都是自洽的(集合中每个元素都不违反题目的规定)
使用并查集的目的就是尽量的把路径压缩,使之高度尽量矮

把两个集合合并成一个集合。
直接
int a = findParent(ani[X]);
int b = findParent(ani[Y]);
ani[b].parent = a;
就是把Y所在集合的根节点的父亲设置成X所在集合的根节点。
但是,但是!!!!
Y所在集合的根结点与X所在集合的根节点的关系!!!要怎么确定呢?
我们设X,Y集合都是路径压缩过的,高度只有2层
我们先给出计算的公式
ani[b].relation = ( 3 - ani[Y].relation + ( d - 1 ) + ani[X].relation) % 3;
这个公式,是分三部分,这么推出来的
第一部分:
( d - 1 ) :这是X和Y之间的relation,X是Y的父节点时,Y的relation就是这个
父相对于子的relation(即假如子是父的父节点,那么父的relation应该是什么,因为父现在是根节点,所以父.relation = 0,我们只能根据父的子节点反推子跟父节点的关系)
0 ( 3 - 0 ) % 3 = 0
1(父吃子) ( 3 - 1 ) % 3 = 2 //父吃子
2(子吃父) ( 3 - 2 ) % 3 = 1 //子吃父
——————————————————————————————————————————————————————
我们的过程是这样的:
把ani[Y],先连接到ani[X]上,再把ani[Y]的根节点移动到ani[X]上,最后,把ani[Y]的根节点移动到ani[X]的根节点上,这样算relation的
还记得么,如果我们有一个集合,压缩路径的时候父子关系是这么确定的
ani[爷爷].relation = ( ani[父亲].relation + ani[儿子].relation ) % 3
我们已知道,( d - 1 )就是X与Y的relation了
而 (3 - ani[Y].relation)就是 以Y为根节点时,他的父亲的relation
我们假设把Y接到X上,也就说,现在X是Y的父亲,Y原来的根节点现在是Y的儿子
Y的relation + ani[Y]根节点相对于ani[Y]的relation
( ( d - 1 ) + ( 3 - ani[Y].relation) ) % 3
就是ani[Y]的父亲节点与ani[X]的relation了!

那么,不难得到,ani[Y]的根节点与ani[X]根节点的关系是:
( ( d - 1 ) + ( 3 - ani[Y].relation) + ani[X].relation ) % 3 ->应用了同余定理
注意,这个当所有集合都是初始化状态的时候也适用哦
Part III - 算法正确性的证明
首先,两个自洽的集合,合并以后仍然是自洽的
当set1和set2合并之后,set2的根节点得到了自己关于set1根节点的
正确relation值,变成了set1根节点的儿子,那么
set2的所有儿子只要用
( ani[X].relation + ani[Y].relation ) % 3就能得到自己正确的relation值了
所以说,针对不在同一集合的两个元素的话,除非违背了(2)和(3),否则永远是真的
(无论这句话说的是什么,我们都可以根据所给X,Y推出两个子节点之间应有的关系,这个关系一确定,所有儿子的关系都可以确定)

其实所有的不同集合到最后都会被合并成一个集合的。
我们只要在一个集合中找那些假话就可以了。
首先,如何判断
1 X Y是不是假话。//此时 d = 1
if ( X 和 Y 不在同一集合)
Union(x,y,xroot,yroot,d)
else
if x.relation != y.relation ->假话
其次,如何判断
2 X Y是不是假话 //此时d = 2
if ( X 和 Y 不在同一集合)
Union(x,y,xroot,yroot,d)
else
(ani[y].relation + 3 - ani[x].relation ) % 3 != 1 ->假话
这个公式是这么来的:
3 - ani[x].relation得到了根节点关于x的relation
ani[y] + 3 - ani[x].relation得到了y关于x的relation
所以,只要y关于x的relation不是1,就是y不被x吃的话,这句话肯定是假话!

(2)路径压缩要特别注意的一点
路径压缩的时候,记得要先findParent,再给当前节点的relation赋值。
否则有可能因为当前节点的父节点的relation不正确而导致错的稀里哗啦。

#include<cstdio>
using namespace std;
const int N=50010;
struct animal{
	int fa,rel;
}ani[N];
int n,k,d,x,y,a,b,ans;
void init_animal(int n){
	for (int i=1;i<=n;i++){
		ani[i].fa=i;
		ani[i].rel=0;
	}
}
int findparent(int x){
	if (ani[x].fa==x)return ani[x].fa;
	int tmp;
	tmp=ani[x].fa;//因为ani[x].fa的值在下一步中可能改变了
	ani[x].fa=findparent(ani[x].fa);
	ani[x].rel=(ani[x].rel+ani[tmp].rel)%3;
	return ani[x].fa;
}
void Union(int x,int y,int a,int b,int d){
	ani[b].fa=a;
	ani[b].rel=((3-ani[y].rel)+(d-1)+ani[x].rel)%3;
}
int main(){
	scanf("%d%d",&n,&k);
	init_animal(n);
	for (int i=1;i<=k;i++){
		scanf("%d%d%d",&d,&x,&y);
		if (x>n||y>n) ans++;
		else if (d==2 && x==y)ans++;
		else{
			a=findparent(x);b=findparent(y);
			if (a!=b) Union(x,y,a,b,d);
			else{
				if (d==1){
					if (ani[x].rel!=ani[y].rel) ans++;
				}
				else if (((ani[y].rel+3-ani[x].rel)%3)!=1) ans++;
			}
		}
	}
	printf("%d",ans);
}

  

时间: 02-28

【NOI2001】食物链的相关文章

Noi2001食物链-并查集

并查集当par[a]==par[b]时就不需要处理合并(a,b)的操作了.下面附标程: 1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 int ans,n,k; 7 struct st{ 8 int par,len; 9 }; 10 int len[50001],par[50001]; 11 v

食物链

题目描述 动物王国中有三类动物 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 句话有的是真 的,有的是假的.当

poj 1182 食物链

食物链 题意:"1 X Y",表示X和Y是同类;"2 X Y",表示X吃Y;输入N(1 <= N <= 50,000),(0 <= K <= 100,000)表示最多有N个动物,同时有K句话. 如果当前的话与前面的话不矛盾就说当前的话是正确的:(无罪判定)问这K句话中有几句是假话: 思路:很裸的种类并查集,只是里面穿插了三种关系,即同类,A吃B,B吃A:其实看了数组的范围[3*N]和x+N,x+2*N就知道思路了:即x吃x+N;类推 对于判定

NOI 2001 &amp; luogu P2024 &amp; POJ 1182食物链

食物链 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 71707   Accepted: 21240 Description 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形.A吃B, B吃C,C吃A. 现有N个动物,以1-N编号.每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种. 有人用两种说法对这N个动物所构成的食物链关系进行描述: 第一种说法是"1 X Y",表示X和Y是同

POJ1182 食物链---(经典种类并查集)

题目链接:http://poj.org/problem?id=1182 食物链 Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 69207   Accepted: 20462 Description 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形.A吃B, B吃C,C吃A. 现有N个动物,以1-N编号.每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种. 有人用两种说法对这N个动物所构成的食

【POJ1182】 食物链 (带权并查集)

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句话有的是真的,有的是假的.当一句话满足下列三条之

tyvj1202 数数食物链

描述 TsyD学习了生物的生态环境那一张后,老师留了一项作业,就是给一张食物网,求所有食物链的总数.(从最低营养级生物(它不能吃任何其他的生物)开始到最高营养级(它不能被任何其他生物吃) 叫做一条食物链)输入保证所有的生物之间都有直接或间接的生存关系 输入格式 第一行 N,M 分别表示有N(N<=50000)个生物,M(M<=100000)个吃的关系接下来M行 每行有两个值a,b 分别 表示b吃a (编号从1开始) 输出格式 食物链的总数 MOD 11129 的值 测试样例1 输入 3 3 1

POJ 1182 :食物链(并查集)

食物链 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

poj 2912 并查集(食物链加强版)

题目:给出n个人玩剪刀石头布的游戏,其中有一个人是裁判,剩下的人分为3组,每一组的人只出某一种手型,裁判可以任意出.问是否能判断出哪个人是裁判 链接:点我 分分钟看吐血,先把食物链看懂吧 枚举裁判,然后并查集判断 裁判由于可以任意出,所以可能属于任意一个集合,所以有裁判参与的会合不考虑,然后并查集部分和食物链很相似. 如果某个裁判那里出现了矛盾,则记录一下在哪出问题. 然后判断是否只有一个裁判没有出现问题.如果只有一个,说明可以确定,那么就是剩下的人出问题的最大值.因为只有否定了其它所有人,才能