1901 最长链(图论算法)

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

1、【莞中、松山湖noip2010联合测试（一）】最长链（图论算法）TimeLimit:10000MS MemoryLimit:265536KTotalSubmit:3Accepted:3Description最长链(chain)【问题描述】　　现给出一棵N个结点二叉树，问这棵二叉树中最长链的长度为多少，保证了1号结点为二叉树的根。Input　　输入文件chain.in的第1行为包含了一个正整数N，为这棵二叉树的结点数，结点标号由1至N。　　接下来N行，这N行中的第i行包含两个正整数l[i],r[i]，表示了结点i的左儿子与右儿子编号。如果l[i]为0，表示结点i没有左

2、儿子，同样地，如果r[i]为0则表示没有右儿子。Output　　输出文件chain.out包括1个正整数，为这棵二叉树的最长链长度。SampleInput6234506000000SampleOutput4Hint【样例说明】　　4-2-1-3-6为这棵二叉树中的一条最长链。【数据规模】　　对于10%的数据，有N≤10；　　对于40%的数据，有N≤100；　　对于50%的数据，有N≤1000；　　对于60%的数据，有N≤10000；　　对于100%的数据，有N≤100000，且保证了树的深度不超过32768。【提示】关于二叉树：　　二叉树的递归定义：二叉树要么为空，

3、要么由根结点，左子树，右子树组成。左子树和右子树分别是一棵二叉树。　　请注意，有根树和二叉树的三个主要差别：　　　1、树的结点个数至少为1，而二叉树的结点个数可以为0；　　　2、树中结点的最大度数没有限制，而二叉树结点的最大度数为2；　　　3、树的结点无左、右之分，而二叉树的结点有左、右之分。关于最长链：　　最长链为这棵二叉树中一条最长的简单路径，即不经过重复结点的一条路径。可以容易证明，二叉树中最长链的起始、结束结点均为叶子结点。Source对照1045程序1：varn,max,maxh:longint;l,p:array[1..100000,0..4]oflon

4、gint;procedureinit;vari,i2,j,k,s:longint;beginreadln(n);fori:=1tondofori2:=1to2dobeginread(k);ifk=0thencontinue;j:=i;inc(p[j,0]);inc(p[k,0]);p[j,p[j,0]]:=k;p[k,p[k,0]]:=j;l[j,p[j,0]]:=1;l[k,p[k,0]]:=1;end;end;proceduretr(x,y,s:longint);vari:longint;beginif(p[y,0]>1)or(x=-1)thenbeginfor

5、i:=1top[y,0]doifp[y,i]<>xthentr(y,p[y,i],s+l[y,i]);endelseifs>maxthenbeginmax:=s;maxh:=y;end;end;begininit;tr(-1,1,0);tr(-1,maxh,0);writeln(max);end.程序2：vari,j,n,x,y,z,t,max:longint;a:array[1..100000,1..2]oflongint;ans:array[0..100000]oflongint;f:array[1..100000]ofboolean;proceduretry(

6、n:longint);vari,j,max1,max2:longint;beginf[n]:=false;max1:=0;max2:=0;ans[n]:=1;iff[a[n,1]]thenbegintry(a[n,1]);max1:=ans[a[n,1]];end;iff[a[n,2]]thenbegintry(a[n,2]);max2:=ans[a[n,2]];end;ifmax1>max2thenans[n]:=max1+ans[n]elseans[n]:=max2+ans[n];ifmax

7、inreadln(n);fori:=1tondobeginreadln(x,y);a[i,1]:=x;a[i,2]:=y;end;fillchar(f,sizeof(f),1);max:=0;try(1);writeln(max);end.