《ioi2001 eat 食物链.doc》由会员分享，可在线阅读，更多相关《ioi2001 eat 食物链.doc（4页珍藏版）》请在金锄头文库上搜索。
1、NOI2001_eat 食物链问题描述动物王国中有三类动物a,b,c，这三类动物的食物链构成了有趣的环形。a吃b， b吃c，c吃a。现有n个动物，以1n编号。每个动物都是a,b,c中的一种，但是我们并不知道它到底是哪一种。有人用两种说法对这n个动物所构成的食物链关系进行描述：第一种说法是“1 x y”，表示x和y是同类。第二种说法是“2 x y”，表示x吃y。此人对n个动物，用上述两种说法，一句接一句地说出k句话，这k句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。1. 当前的话与前面的某些真的话冲突，就是假话；2. 当前的话中x或y比n大，就是假话；3.
2、 当前的话表示x吃x，就是假话。你的任务是根据给定的n(1n50,000)和k句话(0k100,000)，输出假话的总数。输入文件第一行是两个整数n和K，以一个空格分隔。以下K行每行是三个正整数D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。若D=1，则表示X和Y是同类。若D=2，则表示X吃Y。输出文件只有一个整数，表示假话的数目。输入输出样例eat.in100 71 101 1 2 1 22 2 3 2 3 3 1 1 3 2 3 1 1 5 5eat.out 3在某些应用中，要将n个不同元素分成一组不相交的集合，不相交集合上有两个重要操作，即找出给定的元素所属的集合和合并两个集合
3、。为了使某种数据结构能够支持这两种操作，就需要对数据结构进行维护。1. 不相交集合上的操作不相交集合数据结构(disjoint-set data structure)保持一组不相交的动态集合s=s1,s2,sn。每个集合通过一个代表来识别，代表即集合中的某个成员。，设x表示一个对象，我们希望支持以下操作：Make-Set(x)，建立一个新的集合，其唯一成员(因而其代表)就是x。因为各集合是不相交的，故要求x没有在其它集合中出现过。Union(x,y)，将包含x和y的动态集合比如说sx和sy合并为一个新的集合(即这两个集合的并集)。假定在这个操作之前两个集合是不相交的。在经过此操作后，所得集合的
4、代表可以是sxsy中的任何成员。但在Union的很多实现中，都选择sx或sy的代表作为新的代表。由于各集合是不相交的，故我们“消除了”集合sx和sy，把它们从s中删去。Find-Set(x)，返回一个指针，指向包含x的(唯一)集合的代表。2. 不相交集合的链表表示要实现不相交集合数据结构，一种简单的方法是每一个集合都用一个链表来表示，每个链表中的第一个对象作为它所在集合的代表。3. 不相交集合森林在不相交集合的另一种更快的实现中，用有根树来表示集合。树中的每个结点都包含集合的一个成员，每棵树表示一个集合。每个成员仅指向其父结点。每棵数的根包含了代表，并且是它自己的父结点。下面是树结构的并查集的
5、两种运算方式 (1) 直接在树中查询 (2) 边查询边“路径压缩对应与前面的链式存储结构，树状结构的优势非常明显：编程复杂度低;时间效率高。 直接在树中查询 集合的合并算法很简单，只要将两棵树的根结点相连即可，这步操作只要O(1)时间复杂度。算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为O(logn)。但在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为O(n)。 边查询边“路径压缩 其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩”算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径压缩后
6、，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数(x)。对于可以想象到的n，(n)都是在5之内的。 以图论题分析：以动物为点，动物之间的大小关系为边。由于动物分三类，且动物之间互相制约，因此用1，2，3描述它们之间的大小关系，若动物A动物B存在有向关系，则动物B减动物A关系的差值 mod 3_ 环行食物链对应模3的关系：1. 并查集的数据结构fa为结点的父指针序列，ch为结点的权序列，var fa:array1.50000 of longint; ch:array1.50000 of 0.2; i,k,x,y,n,d,tot:longint; fin,fout:text
7、;2. 寻找树根，进行路径压缩function fath(now:longint):longint;var k:longint;begin if fanow=0 then exit(now); if fafanow=0 then exit(fanow); k:=fath(fanow); 对now的父结点所在的子树进行路径压缩，计算调整后的now的祖父结点 chnow:=(chnow+chfanow) mod 3; fanow:=k; exit(k); 递归回溯后，now的父结点调整为子树的根结点，函数返回值为now的父结点 end;3. 合并子树，判断假话procedure solve(d1,
8、x,y:longint);var p,q:longint;begin p:=fath(x); q:=fath(y);分别对X，Y所在的子树进行路径压缩，并计算它们父结点的序号 if p=q then若X，Y在同一棵树内(动物X和动物Y的关系确定) begin if (3-chx+chy) mod 3d-1 then inc(tot); exit; end; faq:=p; 若X，Y不在同一棵树内，合并子树。Y所在子树的根结点调整为X的子树的根结点 chq:=(3+d1-chy+chx) mod 3; 根据调整后的X和Y关系，修改Y结点的权end;begin assign(fin,eat10.i
9、n);reset(fin); assign(fout,eat.out);rewrite(fout); readln(fin,n,k); tot:=0; for i:=1 to k do begin readln(fin,d,x,y); if (xn)or(yn)or(d=2)and(x=y) then inc(tot)若是第2、3类假话，则计数+1 else solve(d-1,x,y); 不是第2、3类假话，判断 end; writeln(fout,tot); close(fin);close(fout);end.var fa:array1.50000 of longint; ch:arra
10、y1.50000 of 0.2; i,k,x,y,n,d,tot:longint;function fath(now:longint):longint;var k:longint;begin if fanow=0 then exit(now); if fafanow=0 then exit(fanow); k:=fath(fanow); chnow:=(chnow+chfanow) mod 3; fanow:=k; fath:=k;end;procedure solve(d1,x,y:longint);var p,q:longint;begin p:=fath(x); q:=fath(y);
11、if p=q then begin if (3-chx+chy) mod 3d-1 then inc(tot); exit; end; faq:=p; chq:=(3+d1-chy+chx) mod 3;end;begin assign(input,eat.in);reset(input); assign(output,eat.ans);rewrite(output); readln(n,k); tot:=0; for i:=1 to k do begin readln(d,x,y); if (xn)or(yn)or(d=2)and(x=y) then inc(tot)else solve(d-1,x,y); end; writeln(tot); close(input);close(output);end.- 4 - 2010-12-15
