設T=(V, E, W) 是一個無圈且連通的無向圖（也稱為無根樹），每條邊到有正整數的權，我們稱T為樹網（treebetwork），其中V，E分別表示結點與邊的集合，W表示各邊長度的集合，並設T有n個結點。
路徑：樹網中任何兩結點a，b都存在唯一的一條簡單路徑，用d(a, b)表示以a, b為端點的路徑的長度，它是該路徑上各邊長度之和。我們稱d(a, b)為a, b兩結點間的距離。
D(v, P)=min{d(v, u), u為路徑P上的結點}。
樹網的直徑：樹網中最長的路徑成為樹網的直徑。對於給定的樹網T，直徑不一定是唯一的，但可以證明：各直徑的中點（不一定恰好是某個結點，可能在某條邊的內部）是唯一的，我們稱該點為樹網的中心。
偏心距ECC(F)：樹網T中距路徑F最遠的結點到路徑F的距離，即
ECC(F)=max{d(v, F)，v∈V}
任務：對於給定的樹網T=(V, E, W)和非負整數s，求一個路徑F，他是某直徑上的一段路徑（該路徑兩端均為樹網中的結點），其長度不超過s（可以等於s），使偏心距ECC(F)最小。我們稱這個路徑為樹網T=(V, E, W)的核（Core）。必要時，F可以退化為某個結點。一般來說，在上述定義下，核不一定只有一個，但最小偏心距是唯一的。
下面的圖給出了樹網的一個實例。圖中，A-B與A-C是兩條直徑，長度均為20。點W是樹網的中心，EF邊的長度為5。如果指定s=11，則樹網的核為路徑DEFG（也可以取為路徑DEF），偏心距為8。如果指定s=0（或s=1、s=2），則樹網的核為結點F，偏心距為12。
5 2
1 2 5
2 3 2
2 4 4
2 5 3
5
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
5
本題為NOIP2007提高組第四題，是不是感覺題目都不想看？各種專有名詞，篇幅極長，總會有點抵觸心理的。但是，說實話這道題真不難，把題目的意思濃縮一下就是要你求一段最長的路徑，然後在整個圖中的每一個點到該路徑上的點的最大長度的最小值即是答案。而且這段路徑上長度不超過s的路徑才可以去找，甚至這條路徑可能是一個點。
明白題目之後就很好辦了，首先floyed把所有路徑長求出來，然後在其中找最大值，那麼怎麼判斷我們要找的路徑（點）在直徑上呢？可以這麼做：如果從直徑的起點出發到該路徑（點）的距離與該路徑到直徑的終點的距離相加為直徑的距離則說明該路徑（點）在直徑上。那麼，怎麼確定一條路徑上所有的點呢？這裡，我用road[i,j]記錄i-j這條路徑上j的前一個節點，至於怎麼更新，詳見代碼，大家可以把這個方法記下來。然後就是求最大值和求最小值的問題了。
1 var n,s,i,j,x,y,z,k,max,min,maxlen,maxi,maxj,q,minx:longint; 2 a,road:array[1..300,1..300] of longint; 3 begin 4 readln(n,s); 5 for i:=1 to n do 6 for j:=1 to n do 7 a[i,j]:=maxint; 8 for i:=1 to n-1 do 9 begin 10 readln(x,y,z); 11 a[x,y]:=z; 12 a[y,x]:=z; 13 road[x,y]:=x; 14 road[y,x]:=y;//road數組初始化 15 end; 16 for k:=1 to n do 17 for i:=1 to n do 18 for j:=1 to n do 19 if a[i,k]+a[k,j]<a[i,j] then 20 begin 21 a[i,j]:=a[i,k]+a[k,j]; 22 road[i,j]:=road[k,j];//隨floyed的更新而更新 23 end; 24 min:=maxlongint; 25 for i:=1 to n do 26 begin 27 road[i,i]:=0; 28 a[i,i]:=0; 29 end; 30 for i:=1 to n do 31 for j:=1 to n do 32 if a[i,j]>maxlen then 33 begin 34 maxlen:=a[i,j]; 35 maxi:=i; 36 maxj:=j; 37 end; 38 for i:=1 to n do 39 for j:=1 to n do 40 if (a[i,j]<=s)and(a[maxi,i]+a[i,j]+a[j,maxj]=maxlen) then 41 begin 42 max:=0; 43 for q:=1 to n do 44 begin 45 k:=j; 46 minx:=maxlongint; 47 while k<>0 do 48 begin 49 if a[q,k]<minx then 50 minx:=a[q,k]; 51 k:=road[i,k]; 52 end; 53 if minx>max then 54 max:=minx; 55 end; 56 if max<min then 57 min:=max; 58 end; 59 writeln(min); 60 end.
