全國(guó)青少年信息學(xué)奧林匹克聯(lián)賽復(fù)賽試題、測(cè)試數(shù)據(jù)解題報(bào)告提高組95-10noip2003

第九屆青少年信息學(xué)聯(lián)賽（N0IP2003）復(fù)賽提高組解題報(bào)告作者：省水果湖高中伍先軍:wuxi大榕樹編程世界 收稿時(shí)間20031227題一神經(jīng)網(wǎng)絡(luò)【問(wèn)題背景】人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork）是一種新興的具有自我學(xué)習(xí)能力的計(jì)算系統(tǒng)，在模式經(jīng)網(wǎng)絡(luò)模型的實(shí)用性?！締?wèn)題描述】第九屆青少年信息學(xué)聯(lián)賽（N0IP2003）復(fù)賽提高組解題報(bào)告作者：省水果湖高中伍先軍:wuxi大榕樹編程世界 收稿時(shí)間20031227題一神經(jīng)網(wǎng)絡(luò)【問(wèn)題背景】人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetwork）是一種新興的具有自我學(xué)習(xí)能力的計(jì)算系統(tǒng)，在模式經(jīng)網(wǎng)絡(luò)模型的實(shí)用性?！締?wèn)題描述】元之間至多有一條邊相連，下圖是一個(gè)神經(jīng)元的例子：1）輸出信息，只從上一層神經(jīng)元接受信息。下圖是一個(gè)簡(jiǎn)單的三層神經(jīng)網(wǎng)絡(luò)的例子。蘭蘭規(guī)定，i（n）WiCjUiCiWji（可能為負(fù)值）WiCjUiCiWji（可能為負(fù)值）j號(hào)神經(jīng)元和i號(hào)神經(jīng)元的邊的權(quán)值。當(dāng)Ci0Ci?！，F(xiàn)在，給定一個(gè)神經(jīng)網(wǎng)絡(luò)，及當(dāng)前輸入層神經(jīng)元的狀態(tài)（C【輸入格式】最初狀態(tài)和其閾值（U0Pi，jWiji、jWij?！据敵龈袷健恳钥崭穹指簟H輸出最后狀態(tài)非零的輸出層神經(jīng)元狀態(tài)，并且按照編號(hào)由小到大順序輸出！0，則輸出NULL?！据斎霕永?110006001111415122【輸出樣例】345111[分析]（輸出層在中間層中只有神經(jīng)元處于興奮狀態(tài)時(shí)（Ci>0）才會(huì)向下一層傳送信號(hào)。[PASCALprogramNOIP2003_1_Network;constmaxn=200;maxp=200;vari,j,n,p,maxlayer:integer;w:array[0..maxp]oflongint;{存放邊的權(quán)值}start,terminal:array[0..maxp]ofbyte;{存放邊的起點(diǎn)與終點(diǎn)}u,c:array[0..maxn]oflongint;{存放神經(jīng)元的閥值與狀態(tài)值}u,c:array[0..maxn]oflongint;{存放神經(jīng)元的閥值與狀態(tài)值}layer:array[0..maxn]ofbyte;{存放神經(jīng)元的層數(shù)}f1,f2:text;fn1,fn2,fileNo:string;flag:boolean;beginwrite('InputfileNo:');readln(fileNo);fn1:='network.in'+fileNo;fn2:='network.ou'+fileNo;assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2);readln(f1,n,p);fori:=1tondoreadln(f1,c[i],u[i]);fillchar(layer,sizeof(layer),0);fori:=1topdobeginreadln(f1,start[i],terminal[i],w[i]);{讀入邊的起點(diǎn)，終點(diǎn)，權(quán)}（1）}end;close(f1);求最大層數(shù)，即輸出層的層數(shù)}i:=1tondoiiflayer[i]>0thenbeginforj:=1topdoand(c[start[j]]>0)ij奮時(shí)（Cj>0）Ithenc[i]:=c[i]+w[j]*c[start[j]];c[i]:=c[i]-u[i];end;{輸出結(jié)果}flag:=true;fori:=1tondoif(layer[i]=maxlayer)and(c[i]>0)thenbeginwriteln(f2,i,'',c[i]);flag:=false;end;ifflagthenwriteln(f2,'NULL');close(f2);end.[點(diǎn)評(píng)]基本題。題目閱讀起來(lái)有些費(fèi)神，題中邊的權(quán)值W,神經(jīng)元的狀態(tài)值C,閥值U，均未明確指出其取值范圍，反映出命題不嚴(yán)謹(jǐn)。題二推理【問(wèn)題描述】明明同學(xué)最近迷上了漫畫《柯南》并沉醉于推理之中，于是他召集了一群同學(xué)玩推理。的內(nèi)容是這樣的，明明的同學(xué)們先商量好由其中的一個(gè)人充當(dāng)罪犯（在明明不知情的情況下，明明的任務(wù)就是找出這個(gè)罪犯。接著，明明逐個(gè)詢問(wèn)每一個(gè)同學(xué)，被詢問(wèn)者可能會(huì)說(shuō)：中出現(xiàn)的其他話，都不列入邏輯推理的內(nèi)容。明明所知道的是，他的同學(xué)中有N個(gè)人始終說(shuō)假話，其余的人始終說(shuō)真?，F(xiàn)在，明明需要你幫助他從他同學(xué)的話中推斷出誰(shuí)是真正的，請(qǐng)記住， 只有一個(gè)！【輸入格式】（1≤M20、N（1≤NM）P1≤P≤10題二推理【問(wèn)題描述】明明同學(xué)最近迷上了漫畫《柯南》并沉醉于推理之中，于是他召集了一群同學(xué)玩推理。的內(nèi)容是這樣的，明明的同學(xué)們先商量好由其中的一個(gè)人充當(dāng)罪犯（在明明不知情的情況下，明明的任務(wù)就是找出這個(gè)罪犯。接著，明明逐個(gè)詢問(wèn)每一個(gè)同學(xué)，被詢問(wèn)者可能會(huì)說(shuō)：中出現(xiàn)的其他話，都不列入邏輯推理的內(nèi)容。明明所知道的是，他的同學(xué)中有N個(gè)人始終說(shuō)假話，其余的人始終說(shuō)真?，F(xiàn)在，明明需要你幫助他從他同學(xué)的話中推斷出誰(shuí)是真正的，請(qǐng)記住， 只有一個(gè)！【輸入格式】（1≤M20、N（1≤NM）P1≤P≤10M的明明的同學(xué)數(shù)，N是其中始終說(shuō)謊的人數(shù)，P是證言的總數(shù)。接下來(lái)M行，每行是明明的一個(gè)同學(xué)的名字（英文字母組成，沒(méi)有主格，全部大寫P冒號(hào)和一個(gè)空格，后面是一句，符合前表中所列格式。每行250輸入中 出現(xiàn)連續(xù)的兩個(gè)空格，而且每行開頭和結(jié)尾也沒(méi)有空格?！据敵龈袷健咳绻愕某绦蚰艽_定誰(shuí)是罪犯，則輸出他的名字；如果程序判斷出不止一個(gè)人可能是罪犯，則輸出CannotDetermine；如果程序判斷出沒(méi)有人可能成為罪犯，則輸出Impossible?！据斎霕永?15MIKECHARLESKATEMIKE:Iamguilty.MIKE:TodayisSunday.CHARLES:MIKEisguilty．KATE:Iamguilty.KATE:Howareyou??【輸出樣例】MIKE[分析]基本思路有兩種：一是可以窮舉M個(gè)人中有N個(gè)人始終說(shuō)假話的所有組合，據(jù)此出發(fā)，判斷每句證詞的真?zhèn)?，再推斷誰(shuí)是罪犯，但這樣做運(yùn)算量大；二是可以窮舉M個(gè)人中的任意一個(gè)是罪犯，由此再來(lái)判斷每句不能說(shuō)找到 人是罪犯或可能是罪犯；二，如何處理關(guān)于的呢？還是可以采用窮舉；三， 的可能前后，在給標(biāo)記他是始終說(shuō)真他此前的誠(chéng)信；因此，對(duì)的誠(chéng)信要有4種不同的區(qū)分，可用0表示此人尚無(wú)有效（未說(shuō)過(guò)真話也未說(shuō)過(guò)假話12數(shù)一定要等于n，而是只要誠(chéng)信；四，如何判斷最初窮舉時(shí)設(shè)定的前提（為3，則肯定不是本題的解；但是也不能強(qiáng)求誠(chéng)信2nm-n錄為0的人可能說(shuō)真話也可能說(shuō)假話，他們只是沒(méi)有說(shuō)話，或只說(shuō)了廢話。五，由于要反復(fù)用于判斷，的?？梢韵忍蕹渲械臒o(wú)效[PASCAL；為處理方便，將有效分為兩部分：不含的和含programNOIP2003_2_Logic;constmaxm=20;dow:array[1..7]ofstring=('Sunday.','Monday.','Tuesday.','Wednesday.','Thursday.','Friday.','Saturday.');varname:array[1..maxm]ofstring;{存放人名}byte;{存放說(shuō)話人的序號(hào),分為兩類,前者存放不含的證的 的說(shuō)話人的序號(hào)}witness1,witness2:array[1..100]ofstring;{存放,分為兩類,第一類是不含的,第二類是只含的不能說(shuō)找到 人是罪犯或可能是罪犯；二，如何處理關(guān)于的呢？還是可以采用窮舉；三， 的可能前后，在給標(biāo)記他是始終說(shuō)真他此前的誠(chéng)信；因此，對(duì)的誠(chéng)信要有4種不同的區(qū)分，可用0表示此人尚無(wú)有效（未說(shuō)過(guò)真話也未說(shuō)過(guò)假話12數(shù)一定要等于n，而是只要誠(chéng)信；四，如何判斷最初窮舉時(shí)設(shè)定的前提（為3，則肯定不是本題的解；但是也不能強(qiáng)求誠(chéng)信2nm-n錄為0的人可能說(shuō)真話也可能說(shuō)假話，他們只是沒(méi)有說(shuō)話，或只說(shuō)了廢話。五，由于要反復(fù)用于判斷，的?？梢韵忍蕹渲械臒o(wú)效[PASCAL；為處理方便，將有效分為兩部分：不含的和含programNOIP2003_2_Logic;constmaxm=20;dow:array[1..7]ofstring=('Sunday.','Monday.','Tuesday.','Wednesday.','Thursday.','Friday.','Saturday.');varname:array[1..maxm]ofstring;{存放人名}byte;{存放說(shuō)話人的序號(hào),分為兩類,前者存放不含的證的 的說(shuō)話人的序號(hào)}witness1,witness2:array[1..100]ofstring;{存放,分為兩類,第一類是不含的,第二類是只含的}name0,temp,temp0,temp1,temp2:string;truth,truth0:array[1..maxm]ofbyte;f1,f2:text;fn1,fn2,fileNo:string;flag:boolean;beginwrite('InputfileNo:');readln(fileNo);}readln(f1,m,n,p);fori:=1tomdoreadln(f1,name[i]);total1:=0;total2:=0;fori:=1topdobegin{對(duì)readln(f1,temp);index:=pos(':',temp);預(yù)處理}temp1:=copy(temp,1,index-1);{取得說(shuō)話人temp2:=copy(temp,index+2,length(temp)-index-1);{取得if(temp2='Iamguiltyor(temp2='Iamnotguilty.')forj:=1tomdoifname[j]=temp1thenbegin}then的總數(shù)}記下第一類第total1條 的說(shuō)話人的序號(hào)}total1break;end;}if(pos('isguilty.',temp2)>0)or(pos('isnottemp0:=copy(temp2,1,pos('is',temp2)-1);{取得flag:=false;fork:=1tomdoiftemp0=name[k]thenbeginflag:=true;break;end;ifflagthen{如果 (主語(yǔ))確實(shí)存在}forj:=1tomdoifname[j]=temp1thenbegin{記入到第一類inc(total1);witness10[total1]:=j;witness1[total1]:=temp2;break;end;end;flag:=false;forj:=1to7doguilty.',temp2)>0)thenbegin中}iftemp2='Todayisif(pos('isguilty.',temp2)>0)or(pos('isnottemp0:=copy(temp2,1,pos('is',temp2)-1);{取得flag:=false;fork:=1tomdoiftemp0=name[k]thenbeginflag:=true;break;end;ifflagthen{如果 (主語(yǔ))確實(shí)存在}forj:=1tomdoifname[j]=temp1thenbegin{記入到第一類inc(total1);witness10[total1]:=j;witness1[total1]:=temp2;break;end;end;flag:=false;forj:=1to7doguilty.',temp2)>0)thenbegin中}iftemp2='Todayisflag:=true;break;end;ifflagthen{如果forj:=1tomdoifname[j]=temp1'+dow[j]thenbegin是關(guān)于的判斷}thenbegin{記入到第二類 中}的總數(shù)}記下第二類第total2條 的說(shuō)話人的序號(hào)}total2break;end;}end;close(f1);表示解的個(gè)數(shù)}iifresolution>1thenbreak;{1fillchar(truth,sizeof(truth),0);{誠(chéng)信賦初值為0,表示此人尚無(wú)有效}forj:=1tototal1dobegin{逐條處理第一類}ifwitness1[j]='Iamguilty.'thenbegin{如果 guilty.}ifi=witness10[j]then{如果說(shuō)話人就是罪犯,則本casetruth[i]of為真}0:truth[i]:=1;{如果此人的誠(chéng)信如果此人的誠(chéng)信end1)}3)}else{如果說(shuō)話人不是罪犯,則本casetruth[witness10[j]]of為假}如果此人的誠(chéng)信1:truth[witness10[j]]:=3;{如果此人的誠(chéng)信0,2)}為1(即以前說(shuō)真話),則此人自相3)}end;end;ifwitness1[j]='Iamnotguilty.'thenbegin{如果ifi=witness10[j]then{如果說(shuō)話人是罪犯,則本casetruth[i]of0:truth[i]:=2;1:truth[i]:=3;endnotguilty.}為假}else{如果說(shuō)話人不是罪犯,則本casetruth[witness10[j]]of0:truth[witness10[j]]:=1;2:truth[witness10[j]]:=3;end;end;為真}if(pos('is如果此人的誠(chéng)信1:truth[witness10[j]]:=3;{如果此人的誠(chéng)信0,2)}為1(即以前說(shuō)真話),則此人自相3)}end;end;ifwitness1[j]='Iamnotguilty.'thenbegin{如果ifi=witness10[j]then{如果說(shuō)話人是罪犯,則本casetruth[i]of0:truth[i]:=2;1:truth[i]:=3;endnotguilty.}為假}else{如果說(shuō)話人不是罪犯,則本casetruth[witness10[j]]of0:truth[witness10[j]]:=1;2:truth[witness10[j]]:=3;end;end;為真}if(pos('isguilty.',witness1[j])>0)thenbegin{如果guilty.}temp:=copy(witness1[j],1,pos('isguilty.',witness1[j])-1);{取得 的主語(yǔ)}ifname[i]=tempthen{如果的主語(yǔ)是罪犯,則本casetruth[witness10[j]]of0:truth[witness10[j]]:=1;2:truth[witness10[j]]:=3;end為真}else{如果的主語(yǔ)不是罪犯,則本為假}casetruth[witness10[j]]of0:truth[witness10[j]]:=2;1:truth[witness10[j]]:=3;end;end;if(pos('isnotguilty.',witness1[j])>0)thenbegin{如果isnotguilty.}temp:=copy(witness1[j],1,pos('isnotguilty.',witness1[j])-1);{取得 的主語(yǔ)}ifname[i]=tempthen{如果的主語(yǔ)是罪犯,則本casetruth[witness10[j]]of0:truth[witness10[j]]:=2;1:truth[witness10[j]]:=3;end為假}else{如果的主語(yǔ)不是罪犯,則本為真}casetruth[witness10[j]]of0:truth[witness10[j]]:=1;2:truth[witness10[j]]:=3;end;end;end;{第一類 全部處理完畢}iftotal2>0thenbegin{如果有第二類}fork:=1tomdotruth0[k]:=truth[k];{記下第一類全部處理完畢后的誠(chéng)信}forweekday:=1to7dobegin{窮舉,今天是fork:=1tomdotruth[k]:=truth0[k];{誠(chéng)信日,一直到 六}還原為第一類全部處理完畢后的誠(chéng)信}forj:=1tototal2do{逐條處理第二類ifpos(dow[weekday],witness2[j])>0}then{如果 中含有當(dāng)前窮舉的值,則本為真}casetruth[witness20[j]]of0:truth[witness20[j]]:=1;2:truth[witness20[j]]:=3;endelse{如果中不含有當(dāng)前窮舉的為假}casetruth[witness20[j]]of0:truth[witness20[j]]:=2;1:truth[witness20[j]]:=3;end;p1:=0;p2:=0;p3:=0;forforfork:=1k:=1k:=1tototommmdododoifififtruth[k]=1truth[k]=2truth[k]=3thenthenthenforweekday:=1to7dobegin{窮舉,今天是fork:=1tomdotruth[k]:=truth0[k];{誠(chéng)信日,一直到 六}還原為第一類全部處理完畢后的誠(chéng)信}forj:=1tototal2do{逐條處理第二類ifpos(dow[weekday],witness2[j])>0}then{如果 中含有當(dāng)前窮舉的值,則本為真}casetruth[witness20[j]]of0:truth[witness20[j]]:=1;2:truth[witness20[j]]:=3;endelse{如果中不含有當(dāng)前窮舉的為假}casetruth[witness20[j]]of0:truth[witness20[j]]:=2;1:truth[witness20[j]]:=3;end;p1:=0;p2:=0;p3:=0;forforfork:=1k:=1k:=1tototommmdododoifififtruth[k]=1truth[k]=2truth[k]=3thenthenthen的話的人的總數(shù)}if(p1<=m-n)and(p2<=n)and(p3=0)thenbegin{m-n的話,那么當(dāng)前罪犯i就是本題的一個(gè)解}說(shuō)假話的人的總數(shù)小于等于n且沒(méi)有人說(shuō)過(guò)自相name0:=name[i];{記下罪犯的1}break;{end;的窮舉}end;{end;{第二類的窮舉完畢}處理完畢}p1:=0;p2:=0;p3:=0;forforfork:=1k:=1k:=1tototommmdododoifififtruth[k]=1truth[k]=2truth[k]=3thenthentheninc(p1);inc(p2);inc(p3);and(name0<>name[i])thenbegin{為避免重復(fù)計(jì)解,此if(p1<=m-n)and(p2<=n)and(p3=0)處多加了一個(gè)條件:name0<>name[i]}name0:=name[i];inc(resolution);end;end;ifififresolution=1thenwriteln(f2,name0);{如果只有一個(gè)解,則輸出罪犯Impossible}resolution>1thenwriteln(f2,'CannotDetermine');{如果有多個(gè)可能解,則輸出CannotDetermine}close(f2);end.處理關(guān)于的，以及之間是否存在。題三加分二叉樹【問(wèn)題描述】ntree（l,2,3,n題三加分二叉樹【問(wèn)題描述】ntree（l,2,3,n1,2,3,…,n（均為正整數(shù)idtreesubtree（tree）的加分計(jì)算方法如下：subtree＋subtree若某個(gè)子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點(diǎn)本身的分?jǐn)?shù)。不考慮它的空子樹。（1,2,3,…,n）tree。要求輸出；【輸入格式】1（n＜02：n（分?jǐn)?shù)＜100【輸出格式】第1行：一個(gè)整數(shù)，為最高加分（結(jié)果4,000,000,00第2行：n個(gè)用空格隔開的整數(shù)，為該樹的前序遍歷?！据斎霕永?571210【輸出樣例】14531245[分析]很顯然，本題適合用動(dòng)態(tài)規(guī)劃來(lái)解。如果用數(shù)組value[i,j]表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j所組成的二叉樹的最大加分，則動(dòng)態(tài)方程可以表示如下：value[i,j]=max{value[i,i]+value[i+1,j],value[i+1,i+1]+value[i,i]*value[i+2,j],value[i+2,i+2]+value[i,i+1]*value[i+3,j],…,value[j-1,j-1]+value[i,j-2]*value[j,j],value[j,j]+value[i,j-1]}ijroot[i,j]表示[PASCAL{$N+}programNOIP2003_3_Tree;constmaxn=30;vari,j,n,d:byte;a:array[1..maxn]ofbyte;value:array[1..maxn,1..maxn]ofcomp;root:array[1..maxn,1..maxn]ofbyte;p;f1,f2:text;fn1,fn2,fileNo:string;procedurepreorder(p1,p2:byte);{按前序遍歷輸出最大加分二叉樹}beginifp2>=p1thenbeginwrite(f2,root[p1,p2],'');preorder(p1,root[p1,p2]-1);preorder(root[p1,p2]+1,p2);end;end;beginwrite('InputfileNo:');readln(fileNo);procedurepreorder(p1,p2:byte);{按前序遍歷輸出最大加分二叉樹}beginifp2>=p1thenbeginwrite(f2,root[p1,p2],'');preorder(p1,root[p1,p2]-1);preorder(root[p1,p2]+1,p2);end;end;beginwrite('InputfileNo:');readln(fileNo);assign(f1,fn1);reset(f1);assign(f2,fn2);rewrite(f2);readln(f1,n);fori:=1tondoread(f1,a[i]);close(f1);fori:=1tondobeginvalue[i,i]:=a[i];{計(jì)算單個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的加分}root[i,i]:=i;{end;單個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的根節(jié)點(diǎn)}fori:=1ton-1dobeginvalue[i,i+1]:=a[i]+a[i+1];{計(jì)算相鄰兩個(gè)節(jié)點(diǎn)構(gòu)成的二叉樹的最大加分}root[i,i+1]:=i;{02，則最后輸出的前序遍歷結(jié)果是唯一的。}end;dfori:=1ton-ddobeginii+1i+d樹的最大加分}root[i,i+d]:=i;{i}forj:=1toddobegintemp:=value[i+j,i+j]+value[i,i+j-1]*value[i+j+1,i+d];i+jii+diftemp>sthenbegin{如果此值為最大}記下新的最大值和新的根節(jié)點(diǎn)}end;end;i+dii+d-1子樹的二叉樹的最大加分}iftemp>sthenbeginend;value[i,i+d]:=s;end;end;writeln(f2,value[1,n]:0:0);{輸出最大加分}end;end;writeln(f2,value[1,n]:0:0);{輸出最大加分}close(f2);end.點(diǎn)是最大加分二叉樹的前序遍歷序列可能不唯一。題四傳染病控制者，為防止該病在蓬萊國(guó)大范圍流行，該國(guó)決定不惜一切代價(jià)控制傳染病的蔓延。不幸的是，由于人們尚未完全認(rèn)識(shí)這種傳染病，難以準(zhǔn)確判別 攜帶者，更沒(méi)有研制出以保護(hù)易感人群。于是，。經(jīng)過(guò)WHO（蓬萊國(guó)的疾病控制中心決定采取切斷途徑的方法控制疾病生組織）以及全球各國(guó)科研部門的努力，這種新興傳染病的消楚，剩下的任務(wù)就是由你協(xié)助蓬萊國(guó)疾控中心制定一個(gè)有效的控制辦法。具有兩種很特殊的性質(zhì)；途徑是樹型的，一個(gè)人X只可能被某個(gè)特定的人YYXY途徑被切斷，則X就 得病。有周期性，在一個(gè)疾病周期之內(nèi)，傳染病將只會(huì)一代患者，而再給下一代。，并且他們已經(jīng)得到了國(guó)內(nèi)部分易感人群的潛在（一棵樹。但是，麻煩還沒(méi)有結(jié)束。由于蓬萊國(guó)疾控中心人手不夠，同時(shí)也缺乏強(qiáng)大的技術(shù)，以致他們?cè)谝粋€(gè)疾病周期內(nèi)，只能設(shè)法切斷一條 途徑，而沒(méi)有被控制的途徑就會(huì)引起的易感人群被（也就是與當(dāng)前已經(jīng)被的人有途徑相連，且連接途徑?jīng)]有被切斷的人群。當(dāng)不可能有健康人被時(shí)，疾病就中止。所以，蓬萊國(guó)疾控中心要制定出一個(gè)切斷 途徑的順序，以使盡量少的人被你的程序要針對(duì)給定的樹，找出合適的切斷順序。?！据斎敫袷健縩（1≤n≤300）ppij，ij（ij題四傳染病控制者，為防止該病在蓬萊國(guó)大范圍流行，該國(guó)決定不惜一切代價(jià)控制傳染病的蔓延。不幸的是，由于人們尚未完全認(rèn)識(shí)這種傳染病，難以準(zhǔn)確判別 攜帶者，更沒(méi)有研制出以保護(hù)易感人群。于是，。經(jīng)過(guò)WHO（蓬萊國(guó)的疾病控制中心決定采取切斷途徑的方法控制疾病生組織）以及全球各國(guó)科研部門的努力，這種新興傳染病的消楚，剩下的任務(wù)就是由你協(xié)助蓬萊國(guó)疾控中心制定一個(gè)有效的控制辦法。具有兩種很特殊的性質(zhì)；途徑是樹型的，一個(gè)人X只可能被某個(gè)特定的人YYXY途徑被切斷，則X就 得病。有周期性，在一個(gè)疾病周期之內(nèi)，傳染病將只會(huì)一代患者，而再給下一代。，并且他們已經(jīng)得到了國(guó)內(nèi)部分易感人群的潛在（一棵樹。但是，麻煩還沒(méi)有結(jié)束。由于蓬萊國(guó)疾控中心人手不夠，同時(shí)也缺乏強(qiáng)大的技術(shù)，以致他們?cè)谝粋€(gè)疾病周期內(nèi)，只能設(shè)法切斷一條 途徑，而沒(méi)有被控制的途徑就會(huì)引起的易感人群被（也就是與當(dāng)前已經(jīng)被的人有途徑相連，且連接途徑?jīng)]有被切斷的人群。當(dāng)不可能有健康人被時(shí)，疾病就中止。所以，蓬萊國(guó)疾控中心要制定出一個(gè)切斷 途徑的順序，以使盡量少的人被你的程序要針對(duì)給定的樹，找出合適的切斷順序。?！据斎敫袷健縩（1≤n≤300）ppij，ij（ij1是已經(jīng)被 的患者。。其中節(jié)點(diǎn)【輸出格式】的人數(shù)?！据斎霕永?1122336234567【輸出樣例】3[分析]本題關(guān)鍵是要找到切斷傳染途徑的算法，這并不難。以測(cè)試數(shù)據(jù)Epidemic.in5為例說(shuō)明如下：1218121811612如下：，1，8，168，如下圖：這樣，它與圖1十分相似，因此可用遞歸算法來(lái)做。[PASCALprogramNOIP2003_4_Epidemic;constmaxn=300;maxp=300;typenode=array[0..maxp]ofinteger;0iva