资源描述:
《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];ifmax7、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.