《食物链》解题报告.doc

食物链解题报告广东北江中学 方奇问题描述 见Noi2001全国信息学奥赛第一试第一题问题抽象如何判断两个动物之间的关系，是解决本题的关键。对应于图论模型，将每个动物看成一个点，并将在输入数据中出现的有直接联系的每对动物之间连一条边。那么，任两个动物之间存在联系，当且仅当对应的两个点处在同一连同分支中。若将互相有联系的动物归于一个集合，那么本题实际上是一个典型的并查集问题。问题分析并查集的实现，利用树这种数据结构，无论时空上都是最优的。结合本题，描述如下：一棵树对应于一群相互间确定了关系的动物，树的一个结点对应于一个动物。FatherI记录了结点I的父亲，当I为根结点时，有FatherI=0。KindI记录了结点I与父亲的相对关系：1表示I被FatherI吃；2表示I吃FatherI;0表示I与FatherI是同类。当I为根结点时，有KindI=0。算法开始时，FatherI=0,KindI=0，表示先建立n棵不同的树。容易设计出算法的流程真话x,y是否在同一棵树是否和已有关系矛盾读入一句话(d,x,y) 简单 判断后 Y N Y假话 N根据关系d将两树合并 下面来看看关键步骤如何实现。 利用Father,不断上溯，分别找出x、y所属树的根结点Rootx、Rooty。则x、y处在同一棵树中，当且仅当Rootx=Rooty。例如:Rootx=x;While fatherrootx0 dorootx:=fatherrootx; 在中添加运算，得到x、y分别与根的关系d1、d2Rootx:=x;d1:=0;While fatherrootx0 doBegin D1:=(d1+kindrootx) mod 3; Rootx:=fatherrootx; End;从而得到x、y之间的关系d3=(d1+3-d2) mod 3 与相同，先求出d1、d2,在结合x与y之间的关系d，确定出rootx、rooty之间的关系d4=(d1+(d-1)-d2+3) mod 3。合并时只需修改Fatherrooty=rootx、Kindrooty=d4即可。可以看出、本身的耗时都为O(1)，但它们都要借助与的结果。当树退化成一条链时，每次耗时将达到O(n)。于是有必要进行改进。改进一设numroot记录以root为根的树的结点数（不含根），每次合并时总将“小树”合并到“大树”中。随着小树T1合并到大树T2中，T1的每个结点深度增加1，且合并后的T2的结点数至少是T1的结点数的2倍。于是，并查集中的每个结点至多被移动O(logN)次，从而每个结点所在树的高度不会超过O(logN)。所以每次只需O(logN)时间。改进二采用路径压缩技术。即在每次执行的过程中，记录下上溯的路径，将路上所有结点的父亲（Father）都指向根结点。 如图，找结点1的根结点时变化如下:经过上述改进后，算法的时间复杂度大大减少，基本上可以认为是O(N+K)。程序注释Program Eat;var father,kind,num,l1,l2:array1.50000 of longint; i,j,k,n,m,x,y,z,k1,k2,t1,t2,tot:longint; root1,root2:longint; f1,f2:text;procedure init;初始化文件begin assign(f1,eat.in); reset(f1); assign(f2,eat.out); rewrite(f2); readln(f1,n,m);end;procedure main;主过程 procedure Findroot; 上溯出结点的根 begin t1:=0;root1:=x;k1:=0; while root10 do begin inc(t1); l1t1:=root1; k1:=(k1+kindroot1) mod 3; root1:=fatherroot1; end; root1:=l1t1; root1为x的根,k1为x与根的关系 t2:=0;root2:=y;k2:=0; while root20 do begin inc(t2); l2t2:=root2; k2:=(k2+kindroot2) mod 3; root2:=fatherroot2; end root2:=l2t2;root1为x的根,k1为x与根的关系 end; procedure Link1; 当x、y处在同一棵树时，运用路径压缩 var kk:longint; begin j:=t1-1;k:=t2-1; kk:=kindroot1; while (j0)and(k0)and(l1j=l2k) do begin kk:=(kindl1j+kk) mod 3; kindl1j:=kk; fatherl1j:=root1; dec(j);dec(k); end; k1:=kk; while j0 do begin k1:=(kindl1j+k1) mod 3; kindl1j:=k1; fatherl1j:=root1; dec(j); end; k2:=kk; while k0 do begin k2:=(kindl2k+k2) mod 3; kindl2k:=k2; fatherl2k:=root2; dec(k); end; end; procedure Link2; 当x、y不在同一棵树时，将两棵树合并 var kk:longint; begin if numroot1numroot2 then 通过改进条件一，判断哪棵是小树 begin k1:=kindroot1; for j:=t1-1 downto 1 do begin k1:=(kindl1j+k1) mod 3; kindl1j:=k1; fatherl1j:=root1; end; if z=1 then k2:=k1 else k2:=(k1+1) mod 3; for j:=1 to t2 do begin kk:=kindl2j; kindl2j:=k2; k2:=(k2+3-kk) mod 3; fatherl2j:=root1; end; inc(numroot1,numroot2+1); end else begin k2:=kindroot2; for j:=t2-1 downto 1 do begin k2:=(kindl2j+k2) mod 3; kindl2j:=k2; fatherl2j:=root2; end; if z=1 then k1:=k2 else k1:=(k2+2) mod 3; for j:=1 to t1 do begin kk:=kindl1j; kindl1j:=k1; k1:=(k1+3-kk) mod 3; fatherl1j:=root2; end; inc(numroot2,numroot1+1); end; end;begin fillchar(father,sizeof(father),0); fillchar(kind,sizeof(kind),0); fillchar(num,sizeof(num),0); tot:=0; 数组初始化 for i:=1 to m do beginreadln(f1,z,x,y);读如一句话if (xn)or(yn)or(z=2)and(x=y) then进行简单判断 begin inc(tot); continue; end; if x=y then continue;Findroot;执行步骤if root1=root2 then判断x、y是否在同一棵树中 begin if (z=1)and(k1=k2)or(