NOI2001试题：食物链
eat.pas/c/cpp

　　动物王国中有三类动物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），输出假话的总数。

输入文件（eat.in）
　　第一行是两个整数N和K，以一个空格分隔。
　　以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
　　若D=1，则表示X和Y是同类。
　　若D=2，则表示X吃Y。

输出文件（eat.out）
　　只有一个整数，表示假话的数目。

输入样例

输入文件	对7句话的分析
100 7
1 101 1	假话
2 1 2	真话
2 2 3	真话
2 3 3	假话
1 1 3	假话
2 3 1	真话
1 5 5	真话

输出样例
3

食物链问题解题报告

福州一中　陈昊罡

［题意简述］
　　有N个动物，它们分别属于为A,B,C三类，其中A吃B、B吃C、C吃A。数据顺次给出K句话，每句话可以表示其中两个动物X与Y同类或X吃Y两种关系。若当前的话出现以下情况之一时，它就被视为假话：①与以前某句话所确定的种类关系冲突；②X自己吃自己；③X或Y>N。题目要求统计出所有假话的个数。

［算法分析］
　　很显然，对假话条件2、3的处理十分简单，只要在读入数据时作两个条件判断即可解决，题目的主要任务在于处理条件1。
　　从表面上看，条件１的处理似乎也没有什么难度：一个动物无非就是A,B,C三类，而A,B,C之间的食物链关系是一对一单向环形的，也就是说如果已知动物X所属种类和X、Y之间的食物链关系，就一定可以确定出动物Y的种类，同时某个动物具体属于哪一类并不影响本题的结果，而只要求它与其他动物关系的相对位置正确即可。于是，我们不妨开3个数组A,B,C，分别记录着三种类的成员，首先假设第一句有效话中的动物X为A类，将其放入数组A，倘若Y与X同类，则把Y也放入A；若Y被X吃，则将Y放入B，如此反复操作所有的有效话，就可以确定每个动物的种类，并容易统计出假话的个数。（算法一）

　　问题似乎已经圆满地解决了，但是，稍稍认真思考就会发现，上面的这个算法存在着重大的错误，是十分片面的。如下面这个数据所示：

　　按照上面的做法，我们先把1,2放入A，然后由于3吃1，把3放入C；又2吃4，把4放入B。接下来的"2 6 5"却令我们不知所措，因为在此之前没有出现任何有关6或5的关系定义。那么，是不是也可以像开始一样随便找一个种类将它放入呢？比如将5放入A，则6应该放入B，7应该也放入A，这样，最后一行的"1 3 6"就成了假话，因为3和6不在同一组。可是我们完全可以构造出如下的结构，使得该数据的每句话都符合要求：
　　　

　　可见，这个算法只能当每一句话都可直接与此前已知的食物链建立明确关系的时候才能使用。而上面这个数据中，4、5两行中仅仅建立了5,6,7这三个动物的食物链关系，而他们与前面4种动物的关系则是在最后一行才确立起来的。也就是说在此之前1,2,3,4和5,6,7形成了两条互相之间关系未知的食物链，而最后一句话则将这两条链合并为一条。它们之间的关系可以表示为如下的形式：
　　

　　明确了上面这个关系，我们就不难从算法1扩展出另一种算法：对于目前关系未知的动物X，我们为他新开辟一条食物链A2,B2,C2（在此称之为"组"，下同），显然，在这个新的组中，动物X所在的种类也是随意的，于是假设它在A2组，这样，所有与X的关系就可用与算法1同样的方式加入这个组中，而这个组与原先的组A1,B1,C1的关系是不确定的。如此反复，我们也可以得到组3、组4、组5……，一旦有一句话牵涉到某两个组的成员之间的食物链关系，我们就依据一定的换算规则将这两个组合并起来，以保证关系网的完整性。这样，我们得到算法二。

［数据结构定义］
　　type gtype=record
　　　　　　　　　　　g:word; { 动物所属的组，0代表目前不属于任何组 }
　　　　　　　　　　　t:byte; { 动物的种类，0,1,2分别表示A,B,C }
　　　　　　　end;
　　var d:array[1..maxn] of gtype; { 存储N个动物的信息 }
　　　　　　　　　　　cg,n:word; { cg：当前最大组的编号，n:动物总数 }
　　　　　　　　　　　e:longint; { 统计当前假话的个数 }

［算法描述］

　　由于话的个数K比较大，我们采用边读数据边统计的做法。
　　1、 读入一行数据o,x,y（o=1表示x,y同类，o=2表示x吃y）；
　　2、 如果x>n 或 y>n，产生错误，e值加一，返回步骤1；
　　3、 若o=1，same(x,y)；否则 kill(x,y)；

　　两个函数same(x,y)和kill(x,y)定义如下：
　　procedure same(a,b:word); { 用于设置 a,b 同类 }
　　var i,ta,tb,gb:word;
　　begin
　　　if (d[a].g=d[b].g) and (d[a].t=d[b].t) and (d[a].g<>0) then exit;
　　{ 若a,b同组同类，则不进行任何操作 }
　　{ 以下为a,b中至少有一个未分组的情况 }
　　　if (d[a].g=0) and (d[b].g=0) then begin { 若a,b匀尚未分组 }
　　　　inc(cg); { 创建一个新组 }
　　　　d[a].g:=cg; d[a].t:=0; { 把a,b加入这个组，并设为同类 }
　　　　d[b].g:=cg; d[b].t:=0;
　　　　exit;
　　　end;
　　　if (d[b].g=0) then begin { 若a已分组，b未分组 }
　　　　d[b]:=d[a]; exit; { 将b加入a的组，并与a同类 }
　　　end;
　　　if (d[a].g=0) then begin { 若b已分组，a未分组 }
　　　　d[a]:=d[b]; exit; { 将a加入b的组，并与b同类 }
　　　end;
　　{ 以下为a,b均已分组的情况 }
　　　if d[a].g=d[b].g then { 若a,b在同一组，但不同类 }
　　　　inc(e) { 产生错误 }
　　　else begin { 若a,b不在同一组则合并两个组}
　　　　ta:=d[a].t; tb:=d[b].t; gb:=d[b].g;
　　　　for i:=0 to 2 do { 换算a,b两组的等价种类 }
　　　　　r[(tb+i) mod 3]:=(ta+i) mod 3;
　　　　for i:=1 to n do { 遍历所有动物 }
　　　　　if d[i].g=gb then begin { 把所有属于b组的动物 }
　　　　　　　d[i].g:=d[a].g; { 按照换算关系并入a组 }
　　　　　　　d[i].t:=r[d[i].t];
　　　　　end;
　　　end;
　　end;

　　procedure kill(a,b:word); { 用于设置 a吃b }
　　var i,ta,tb,gb:word;
　　begin
　　{ 如果a=b，即自己吃自己，就产生错误 }
　　if a=b then begin inc(e); exit; end;
　　{ 若a,b 同组且a吃b，则不进行任何操作 }
　　if (d[a].g=d[b].g) and (d[b].t=(d[a].t+1) mod 3) and (d[a].g<>0) then exit;
　　{ 以下为a,b中至少有一个未分组的情况 }
　　if (d[a].g=0) and (d[b].g=0) then begin { 若a,b匀尚未分组 }
　　　inc(cg); { 创建一个新组 }
　　　d[a].g:=cg; d[a].t:=0; { 把a,b加入这个组 }
　　　d[b].g:=cg; d[b].t:=1; { 把a设为A类，b设为B类}
　　　exit; { 即设置a吃b }
　　end;
　　if (d[b].g=0) then begin { 若a已分组，b未分组 }
　　　d[b].g:=d[a].g; { 将b加入a的组 }
　　　d[b].t:=(d[a].t+1) mod 3; { 设置b为a的下一类，即a吃b }
　　　exit;
　　end;
　　if (d[a].g=0) then begin { 若b已分组，a未分组 }
　　　d[a].g:=d[b].g; { 将a加入b的组 }
　　　d[a].t:=(d[b].t+2) mod 3; { 设置a为b的下一类，即b吃a }
　　　exit;
　　end;
　　{ 以下为a,b均已分组的情况 }
　　if d[a].g=d[b].g then { 若a,b在同一组，而且同类 }
　　　inc(e) { 产生错误 }
　　else begin { 若a,b不在同一组则合并两个组}
　　　ta:=d[a].t; tb:=d[b].t; gb:=d[b].g;
　　　tb:=(tb+2) mod 3; { 换算a,b两组的等价种类 }
　　　for i:=0 to 2 do
　　　　r[(tb+i) mod 3]:=(ta+i) mod 3;
　　　for i:=1 to n do { 遍历所有动物 }
　　　　if d[i].g=gb then begin { 把所有属于b组的动物 }
　　　　　　d[i].g:=d[a].g; { 按照换算关系并入a组 }
　　　　　　d[i].t:=r[d[i].t];
　　　　end;
　　　end;
　　end;

　　最后，只要输出e的值就可以了。

［算法优化］

　　上面这个算法已经可以完全应付大量的测试数据。经过测试，所有本次NOI的测试数据都可以在0.5秒以内出正确解（Celeron 566 CPU, Free Pascal 1.0.4 for DOS），但是，它还有很大的优化空间。例如，在合并两个组的时候，本算法要遍历所有的动物去寻找与b同组的成员，当n较大的时候其时间代价显然相当大。而Free Pascal给我们提供了很大的内存，所以可以把当前各个组的成员信息全部存在一个链表数组中，这样，我们合并两个组的时候，只要把直接其中一个组的表尾合并到另一个组的表头上即可，这无疑将大大提高速度。另外，上面的算法总是将与b同组的成员合并到a所在的组，当与b同组的元素大大多于与a同组的元素的时候，显然会比将与a同组的成员合并到b所在的组耗时多很多，因此，我们还可以记录下每个组的成员数，合并时有选择的把小的组合并到大的组中。
总之，本题还有很多可以优化的地方值得我们进一步探索。

编者按：本期刊登福州一中几位学生参加者NOI2001网上同步赛后，完成NOI2001试题，写出的解题报告与体会。供大家参考与批评指正。我们希望大家看后能提出你们的见解与你们的解答。我们将给予刊登，希望通过争鸣使大家的算法水平共同提高。来稿请寄fzyzcy@yeah.net