1901最长链(图论算法).doc

《1901最长链(图论算法).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、【莞中、松山湖ｎoiｐ201０联合测试(一)】最长链(图论算法）Timｅ　Ｌiｍｉt:10000ＭＳ MeｍoｒyLimit：２65536ＫTotal　Sｕbmｉｔ：３Ａccｅｐｔed：3　Deｓｃｒipｔion最长链(chａin)　ﻫﻫ【问题描述】ﻫ　现给出一棵N个结点二叉树,问这棵二叉树中最长链的长度为多少，保证了1号结点为二叉树的根。Iｎｐｕt　输入文件chaｉn．in的第1行为包含了一个正整数N，为这棵二叉树的结点数,结点标号由1至N。ﻫ　　接下来N行,这N行中的第i行包含两个正整数ｌ[i]，r［i］，表示了结点i的左儿子与右儿子编号。如果ｌ［i］为０，表示结点ｉ没有左儿子,同样

2、地，如果r[i］为0则表示没有右儿子。Output　输出文件chａin.ｏｕt包括1个正整数，为这棵二叉树的最长链长度。SampleＩnput62　3４　506０　０0００0SamｐleOutpuｔ4Ｈｉnt【样例说明】　4—2－1—3－6为这棵二叉树中的一条最长链。ﻫ【数据规模】　对于１0%的数据，有Ｎ≤10;　ﻫ　　对于40％的数据，有N≤100；ﻫ对于50％的数据，有N≤1000；　　对于60％的数据，有Ｎ≤10000;　　对于10０%的数据，有N≤100000，且保证了树的深度不超过32768。ﻫ【提示】ﻫ关于二叉树:ﻫ二叉树的递归定义：二叉树要么为空，要么由根结点，左子树，右子

3、树组成。左子树和右子树分别是一棵二叉树。ﻫ请注意,有根树和二叉树的三个主要差别：ﻫ　　　1、树的结点个数至少为１，而二叉树的结点个数可以为0;　2、树中结点的最大度数没有限制，而二叉树结点的最大度数为2;　　3、树的结点无左、右之分,而二叉树的结点有左、右之分.　ﻫ关于最长链：ﻫ　最长链为这棵二叉树中一条最长的简单路径，即不经过重复结点的一条路径.可以容易证明，二叉树中最长链的起始、结束结点均为叶子结点.　Sourcｅ对照104５程序1：vａrｎ，max，maxh:lonｇiｎt；l，p:arraｙ[1．.100０００,0.。4]　ｏfｌｏｎgint；pｒoｃedｕrｅinit；vaｒi

4、，ｉ2,j，ｋ,ｓ:ｌongint；ｂｅｇin　readｌn（n）;foｒ　i：=1tｏndｏ　　foｒi2：＝1to2do　begin　　read（k）；　　　if　k=0ｔｈen　ｃoｎtｉnuｅ；　　j：=ｉ;　　inc(p[j,0])；inｃ（p［k，０］）；　p[j，p[j,0］］：=k；ｐ［k,p［ｋ，0］］:=j;　l[ｊ，p［j,0］]:＝1;　l［ｋ，p[k，0］］:=1；enｄ;ｅｎd；pｒｏceduｒetr(x,y，s:longint);vari:ｌoｎｇｉnt;begiｎ　if(p［y,0]＞１）or　(x＝－１)thｅnbegin　for　i：=１　top[ｙ，

5、0］ｄoifp［ｙ,i]＜＞xtheｎ　tｒ(y,ｐ[y,i］，s+l［y,i］）;　ｅnｄelsｅ　ifs〉maxｔhｅn　beginmax：=s;　ｍaxh：=ｙ；eｎd；eｎｄ；begin　ｉnit;tr（—1，１，0)；　tr（-1,ｍａxｈ,０)；　ｗriｔeln（maｘ);ｅnd。程序2：vaｒi，j,n，x,y，z,t,mａx：ｌonｇint；　a：ａｒray［１.。100０００,１.．2］oｆlongiｎｔ；　　ａnｓ:arraｙ［0.。1０００00］ｏfｌｏｎgｉnｔ;f:arｒay［1.。１0０000］oｆbooｌean；ｐroceduretry（n：loｎgｉnt)

6、;vaｒｉ，j，max1,ｍax２：lonｇint;bｅｇin　　　f[n]：=falｓe;max１：=０;　maｘ2：＝0；ans［n]：=1;iff［a[n,1]］tｈｅnbegin　　try(a［n，1］）;ｍax１：=aｎｓ［a[n，1］]；　end；　ifｆ［a［n，2]]theｎbeｇin　try(a[n,2])；max２:＝aｎｓ[a［n,２］］；ｅnd；　ｉf　max１＞ｍax2ｔhｅnaｎs［n］:=max1＋anｓ［n]　ｅlｓeａns［n]:=max２+ａnｓ[ｎ］；　　　iｆ　max＜ｍax1+max2　tｈenmax:=max１＋mａｘ２；enｄ；bｅgｉnre

7、aｄln（n)；　forｉ：＝１toｎdobegin　　rｅadｌn（x,y）；　　　　ａ［i，1]：=x；a[i,2]：=y；　ｅnd;　fillchar（f，ｓiｚｅof（f),１）；max:=0；try(1）；　wrｉteln（mａx);end。