《食物链》解题报告

《《食物链》解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《食物链》解题报告广东北江中学方奇问题描述见Noi2001全国信息学奥赛第一试第一题问题抽象如何判断两个动物之间的关系，是解决本题的关键。对应于图论模型，将每个动物看成一个点，并将在输入数据中出现的有直接联系的每对动物之间连一条边。那么，任两个动物之间存在联系，当且仅当对应的两个点处在同一连同分支中。若将互相有联系的动物归于一个集合，那么本题实际上是一个典型的并查集问题。问题分析并查集的实现，利用树这种数据结构，无论时空上都是最优的。结合本题，描述如下：一棵树对应于一群相互间确定了关系的动物，树的一个结点对应于一个动物。Father[I]

2、记录了结点I的父亲，当I为根结点时，有Father[I]=0。Kind[I]记录了结点I与父亲的相对关系：1表示I被Father[I]吃；2表示I吃Father[I];0表示I与Father[I]是同类。当I为根结点时，有Kind[I]=0。算法开始时，Father[I]=0,Kind[I]=0，表示先建立n棵不同的树。容易设计出算法的流程真话x,y是否在同一棵树是否和已有关系矛盾读入一句话(d,x,y)简单判断后YNY假话N根据关系d将两树合并下面来看看关键步骤如何实现。利用Father,不断上溯，分别找出x、y所属树的根结点Rootx

3、、Rooty。则x、y处在同一棵树中，当且仅当Rootx=Rooty。例如:Rootx=x;Whilefather[rootx]<>0dorootx:=father[rootx];在中添加运算，得到x、y分别与根的关系d1、d2Rootx:=x;d1:=0;Whilefather[rootx]<>0doBeginD1:=(d1+kind[rootx])mod3;Rootx:=father[rootx];End;从而得到x、y之间的关系d3=(d1+3-d2)mod3与相同，先求出d1、d2,在结合x与y之间的关系d，确定出rootx、ro

4、oty之间的关系d4=(d1+(d-1)-d2+3)mod3。合并时只需修改Father[rooty]=rootx、Kind[rooty]=d4即可。可以看出、本身的耗时都为O(1)，但它们都要借助与的结果。当树退化成一条链时，每次耗时将达到O(n)。于是有必要进行改进。改进一设num[root]记录以root为根的树的结点数（不含根），每次合并时总将“小树”合并到“大树”中。随着小树T1合并到大树T2中，T1的每个结点深度增加1，且合并后的T2的结点数至少是T1的结点数的2倍。于是，并查集中的每个结点至多被移动O(logN)次，从而每个

5、结点所在树的高度不会超过O(logN)。所以每次只需O(logN)时间。改进二采用路径压缩技术。即在每次执行的过程中，记录下上溯的路径，将路上所有结点的父亲（Father）都指向根结点。如图，找结点1的根结点时变化如下:经过上述改进后，算法的时间复杂度大大减少，基本上可以认为是O(N+K)。程序注释ProgramEat;varfather,kind,num,l1,l2:array[1..50000]oflongint;i,j,k,n,m,x,y,z,k1,k2,t1,t2,tot:longint;root1,root2:longint;f

6、1,f2:text;procedureinit;{初始化文件}beginassign(f1,'eat.in');reset(f1);assign(f2,'eat.out');rewrite(f2);readln(f1,n,m);end;proceduremain;{主过程}procedureFindroot;{上溯出结点的根}begint1:=0;root1:=x;k1:=0;whileroot1<>0dobegininc(t1);l1[t1]:=root1;k1:=(k1+kind[root1])mod3;root1:=father[r

7、oot1];end;root1:=l1[t1];{root1为x的根,k1为x与根的关系}t2:=0;root2:=y;k2:=0;whileroot2<>0dobegininc(t2);l2[t2]:=root2;k2:=(k2+kind[root2])mod3;root2:=father[root2];endroot2:=l2[t2];{root1为x的根,k1为x与根的关系}end;procedureLink1;{当x、y处在同一棵树时，运用路径压缩}varkk:longint;beginj:=t1-1;k:=t2-1;kk:=ki

8、nd[root1];while(j>0)and(k>0)and(l1[j]=l2[k])dobeginkk:=(kind[l1[j]]+kk)mod3;kind[l1[j]]:=kk;fath