題面在最下方。

樹結(jié)構(gòu)的題做多了就會(huì)發(fā)現(xiàn)，本題所謂的樹網(wǎng)的核（一段偏心距ECC最小的路徑）一定是在樹的直徑上的。

我剛開始做的時(shí)候沒想到這個(gè)，然后寫了三個(gè)dfs討論每條直徑 Orz

其實(shí)只要認(rèn)識到了這一點(diǎn)，那么這個(gè)題maxn=300，輕輕松松打暴力啊！

?

首先跑一次最短路得到整張圖內(nèi)點(diǎn)對<s,t>的距離 （Floyed是可以過的，但是我比較喜歡枚舉每個(gè)點(diǎn)進(jìn)行spfa）

兩個(gè)for枚舉一條路徑的兩個(gè)端點(diǎn)（假設(shè)是 < i ,?j?>）

如果?dis<i,j>?≤?s，就計(jì)算偏心距并更新答案。

算<i,j>的偏心距：再一次枚舉所有點(diǎn)，設(shè)為s，計(jì)算s到路徑<i,j>的距離D。由樹結(jié)構(gòu)的特殊性可以證明，D=（dis<s,i>+dis<s,j>-dis<i,j>）/ 2

那么偏心距就是所有D里面的最大值。同時(shí)ans=min(ans，偏心距)

最后輸出ans即可

?

附上AC代碼

1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 template<class T> inline void read(T &_a){ 6 bool f=0;int _ch=getchar();_a=0; 7 while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();} 8 while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();} 9 if(f)_a=-_a; 10 } 11 12 const int maxn=301,maxs=1001; 13 struct edge 14 { 15 int to,dis,next; 16 }w[maxn<<1]; 17 int n,s,egcnt=1,head[maxn],dis[maxn][maxn],ans=0x7fffffff,h,tail,q[10001]; 18 bool ins[maxn]; 19 20 inline void addedge(int from,int to,int dis) 21 { 22 w[++egcnt].dis=dis; 23 w[egcnt].to=to; 24 w[egcnt].next=head[from]; 25 head[from]=egcnt; 26 w[++egcnt].dis=dis; 27 w[egcnt].to=from; 28 w[egcnt].next=head[to]; 29 head[to]=egcnt; 30 } 31 32 inline void spfa(int u) 33 { 34 memset(ins,0,sizeof(ins)); 35 h=0; tail=1; q[1]=u; dis[u][u]=0; 36 while(h!=tail) 37 { 38 h=h%10000+1; 39 int now=q[h]; 40 ins[now]=false; 41 for (register int i=head[now];i;i=w[i].next) 42 { 43 if(dis[u][w[i].to]>dis[u][now]+w[i].dis) 44 { 45 dis[u][w[i].to]=dis[u][now]+w[i].dis; 46 if(!ins[w[i].to]) 47 { 48 ins[w[i].to]=true; 49 tail=tail%10000+1; 50 q[tail]=w[i].to; 51 } 52 } 53 } 54 } 55 } 56 57 int main() 58 { 59 read(n); read(s); 60 for (register int i=1,a,b,c;i<n;++i) read(a),read(b),read(c),addedge(a,b,c); 61 memset(dis,0x7f,sizeof(dis)); 62 for (register int i=1;i<=n;++i) spfa(i); 63 for (register int i=1;i<=n;++i) 64 for (register int v=1,maxdis=0;v<=n;++v) 65 if(dis[i][v]<=s) 66 { 67 for(register int j=1;j<=n;++j) 68 maxdis=max(maxdis,dis[i][j]+dis[v][j]-dis[i][v]>>1); 69 ans=min(ans,maxdis); 70 } 71 printf("%d",ans); 72 return 0; 73 } View Code

?

描述

設(shè)T=(V, E, W) 是一個(gè)無圈且連通的無向圖（也稱為無根樹），每條邊到有正整數(shù)的權(quán)，我們稱T為樹網(wǎng)（treebetwork），其中V，E分別表示結(jié)點(diǎn)與邊的集合，W表示各邊長度的集合，并設(shè)T有n個(gè)結(jié)點(diǎn)。

路徑：樹網(wǎng)中任何兩結(jié)點(diǎn)a，b都存在唯一的一條簡單路徑，用d(a, b)表示以a, b為端點(diǎn)的路徑的長度，它是該路徑上各邊長度之和。我們稱d(a, b)為a, b兩結(jié)點(diǎn)間的距離。

D(v, P)=min{d(v, u), u為路徑P上的結(jié)點(diǎn)}。

樹網(wǎng)的直徑：樹網(wǎng)中最長的路徑成為樹網(wǎng)的直徑。對于給定的樹網(wǎng)T，直徑不一定是唯一的，但可以證明：各直徑的中點(diǎn)（不一定恰好是某個(gè)結(jié)點(diǎn)，可能在某條邊的內(nèi)部）是唯一的，我們稱該點(diǎn)為樹網(wǎng)的中心。

偏心距ECC(F)：樹網(wǎng)T中距路徑F最遠(yuǎn)的結(jié)點(diǎn)到路徑F的距離，即

ECC(F)=max{d(v, F)，v∈V}

任務(wù)：對于給定的樹網(wǎng)T=(V, E, W)和非負(fù)整數(shù)s，求一個(gè)路徑F，他是某直徑上的一段路徑（該路徑兩端均為樹網(wǎng)中的結(jié)點(diǎn)），其長度不超過s（可以等于s），使偏心距ECC(F)最小。我們稱這個(gè)路徑為樹網(wǎng)T=(V, E, W)的核（Core）。必要時(shí)，F可以退化為某個(gè)結(jié)點(diǎn)。一般來說，在上述定義下，核不一定只有一個(gè)，但最小偏心距是唯一的。

下面的圖給出了樹網(wǎng)的一個(gè)實(shí)例。圖中，A-B與A-C是兩條直徑，長度均為20。點(diǎn)W是樹網(wǎng)的中心，EF邊的長度為5。如果指定s=11，則樹網(wǎng)的核為路徑DEFG（也可以取為路徑DEF），偏心距為8。如果指定s=0（或s=1、s=2），則樹網(wǎng)的核為結(jié)點(diǎn)F，偏心距為12。

格式

輸入格式

包含n行：

第1行，兩個(gè)正整數(shù)n和s，中間用一個(gè)空格隔開。其中n為樹網(wǎng)結(jié)點(diǎn)的個(gè)數(shù)，s為樹網(wǎng)的核的長度的上界。設(shè)結(jié)點(diǎn)編號以此為1，2，……，n。

從第2行到第n行，每行給出3個(gè)用空格隔開的正整數(shù)，依次表示每一條邊的兩個(gè)端點(diǎn)編號和長度。例如，“2 4 7”表示連接結(jié)點(diǎn)2與4的邊的長度為7。

所給的數(shù)據(jù)都是正確的，不必檢驗(yàn)。

輸出格式

只有一個(gè)非負(fù)整數(shù)，為指定意義下的最小偏心距。

樣例1

樣例輸入1

5 2 1 2 5 2 3 2 2 4 4 2 5 3

樣例輸出1

5

限制

1s

提示

40%的數(shù)據(jù)滿足：5<=n<=15
70%的數(shù)據(jù)滿足：5<=n<=80
100%的數(shù)據(jù)滿足：5<=n<=300, 0<=s<=1000。邊長度為不超過1000的正整數(shù)。

?

P.S.?本題在bzoj1999有加強(qiáng)版，maxn增大至500000，傳送門：http://www.lydsy.com/JudgeOnline/problem.php?id=1999

轉(zhuǎn)載于:https://www.cnblogs.com/jaywang/p/7698525.html

總結(jié)

以上是生活随笔為你收集整理的树网的核 Vijos1362 NOIP2007 树结构 直径 暴搜的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。