Ural1569Networkingthe一的，優(yōu)先考慮滿足條件X的那一棵樹。在規(guī)定當條件X不成立，Di=2di；當條件X成立，Di=2di-1。取出使得Di最大的點ViBFS樹Ti，就是答案。為了敘述的方便，引入下面定義：l(v)=max{d(u,.v)|u,v是一個圖中的點}。樹的中心：樹中l(wèi)(v)最小的點。但以某一定點為根的BFS的深度都相等。這些性質是很顯然的，不再證明。CABCQQAPCP=BC-BP≤AB-BP=D2

QCABCRRAP上，D

D2D

R在BP上，則CP=AC-AP≤AB-D

D2

。同時 2

2

2D 2

證明：當T的直徑為偶數(shù)，且P是)的直徑。所以T’的直徑都不超過T的直徑，即T’一定是該圖的一棵直徑最小生成樹。DB在Q一側。類似的偶數(shù)部分的推理，可以得到 2

CQ的子孫。那么，T”是符合X條件的。另一方面，對于任意一棵符合X條件P為根BFST0，設所有滿PC=l(P)的點C，都Q0的子孫。那么T0的直徑為2l(P)-1=D，且P和Q0是它的唯二的中心。證畢。用Floyd算法與處理所有兩點間的距離?？偹惴◤碗s度是O(n3)constvara:array[1..maxn,1..maxn]oflongint;f:array[1..maxn]ofboolean;fori:=1tonforj:=1tonfi<>jthenfori:=1tomdobeginreadln(j,k);a[j,k]:=1;a[k,j]:=1;end;fork:=1tondofori:=1tondoforj:=1tondoifa[i,k]+a[k,j]<a[i,j]thena[i,j]:=a[i,k]+a[k,j];ans:=0;min:=n;link:=0;fori:=1tondobeginforj:=1tonfa[i,j]>disthendis:=a[i,j];forj:=1tonfa[i,j]=1thenbeginfork:=1tonfa[i,k]=disifa[j,k]<>dis-1thenbeginflag:=false;break;end;ifflagthenbreak;ifflagthendis:=dis*2-1elseifdis<minthenbeginans:=i;min:=dis;ifflagthenlink:=j;end;ifminmod2=0thenf[ans]:=trueelsef[link]:=true;fori:=1tomindoforj:=1tonfa[ans,j]=ithenbeginfork:=1tonfa[ans,k]=i-1ifa[j,k]=1theniff[k]thenbeginflag:=false;break;ifnotflagthenbeginf[j]:=true;wrin(j,'',k);continue;end;fork:=1tonfa[ans,k]=i-1thenifa[j,k]=1thenbeginwrin(j,'',k);break;1569.NetworkingtheTimeLimit:1.0secondMemoryLimit:64MBThere’snotmuchtimeleftuntilthe“Iset”toweropensforbusiness,butacomputernetworkisnotyetinstalledinthebuilding.Thenetworkisexpectedtobeveryrobustandshouldhavelotsofbranches.ThereareNnodesinthetowerthatshouldbeconnectedwiththisnetwork.ThesenodeswereplannedtobeconnectedwithMdirectlinks,withnomorethanonedirectlinkbetweeneachpairofnodes.Tosavesometime,itwasdecidedthatonlythelinksthatarerequiredtomakeaconnectednetworkwillbeinstalled;alltheremainingwiresaregoingtobelaidaftertheopeningceremony.Inordertobeefficientnetworkshouldhavesatisfyonemorerequirement:thealdistancebetweenit’snodesmustbeassmallasposible.DistancebetweenapairofnodesAandBisdefinedasthenumberofintermediatenodesonthepathfromthenodeAtothenodeB.ThelinecontainstwointegersN(2≤N≤100)andM(1≤M≤Eachoftheselinescontainsapairofintegers—numbersofnodesthatareconnectedwithadirectlink.Nodesarenumberedfrom1toN.Thisnetworklayoutisguaranteedtobeconnected,andtherearenolinksconnectinganodewithit