【題解】洛谷P1099（同bzoj1999）[NOIP2007T4]樹網的核 樹的直徑

題目連結

題目描述

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

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

D ( v , P ) = min ⁡ { d ( v , u ) } D(v, P)=\min\{d(v, u)\} D(v,P)=min{d(v,u)}, u u u為路徑 P P P上的結點。

樹網的直徑：樹網中最長的路徑成為樹網的直徑。對于給定的樹網 T T T，直徑不一定是唯一的，但可以證明：各直徑的中點（不一定恰好是某個結點，可能在某條邊的内部）是唯一的，我們稱該點為樹網的中心。

偏心距 E C C ( F ) \mathrm{ECC}(F) ECC(F)：樹網T中距路徑F最遠的結點到路徑FF的距離，即

E C C ( F ) = max ⁡ { d ( v , F ) , v ∈ V } \mathrm{ECC}(F)=\max\{d(v, F),v \in V\} ECC(F)=max{d(v,F),v∈V}

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

下面的圖給出了樹網的一個執行個體。圖中， A − B A-B A−B與 A − C A-C A−C是兩條直徑，長度均為 20 20 20。點 W W W是樹網的中心， E F EF EF邊的長度為 5 5 5。如果指定 s = 11 s=11 s=11，則樹網的核為路徑 D E F G DEFG DEFG（也可以取為路徑 D E F DEF DEF），偏心距為 8 8 8。如果指定 s = 0 s=0 s=0（或 s = 1 s=1 s=1、 s = 2 s=2 s=2），則樹網的核為結點 F F F，偏心距為 12 12 12。

輸入輸出格式

輸入格式：

共 n n n行。

第 1 1 1行，兩個正整數 n n n和 s s s，中間用一個空格隔開。其中 n n n為樹網結點的個數， s s s為樹網的核的長度的上界。設結點編号以此為 1 , 2 , … , n 1,2,…,n 1,2,…,n。

從第 2 2 2行到第 n n n行，每行給出 3 3 3個用空格隔開的正整數，依次表示每一條邊的兩個端點編号和長度。例如，“ 247 2 4 7 247”表示連接配接結點 2 2 2與 4 4 4的邊的長度為 7 7 7。

輸出格式：

一個非負整數，為指定意義下的最小偏心距。

輸入輸出樣例

輸入樣例#1：

5 2

1 2 5

2 3 2

2 4 4

2 5 3

輸出樣例#1：

5

輸入樣例#2：

8 6

1 3 2

2 3 2

3 4 6

4 5 3

4 6 4

4 7 2

7 8 3

輸出樣例#2：

5

說明

40 % 40\% 40%的資料滿足： 5 ≤ n ≤ 15 5 \le n \le 15 5≤n≤15

70 % 70\% 70%的資料滿足： 5 ≤ n ≤ 80 5 \le n \le 80 5≤n≤80

100 % 100\% 100%的資料滿足： 5 ≤ n ≤ 300 , 0 ≤ s ≤ 1000 5 \le n \le 300,0 \le s \le 1000 5≤n≤300,0≤s≤1000。邊長度為不超過 1000 1000 1000的正整數

bzoj上資料增強：

對于 70 % 70\% 70%的資料， n ≤ 200000 n\le200000 n≤200000

對于 100 % 100\% 100%的資料： n ≤ 500000 , s &lt; 2 31 n\le500000, s&lt;2^{31} n≤500000,s<231, 所有權值 &lt; 500 &lt;500 <500

NOIP 2007 提高第四題

設直徑上的節點為 u 1 , u 2 , . . . , u t u_1,u_2,...,u_t u1​,u2​,...,ut​，先把這幾個節點标記為“已通路”，然後通過深度優先周遊，求出 d [ u i ] d[u_i] d[ui​]，表示從 u i u_i ui​出發，不經過直徑上的其他節點，能夠到達的最遠點的距離。

以 u i , u j ( i ≤ j ) u_i,u_j(i\le j) ui​,uj​(i≤j)為端點的樹網的核的偏心距就是：

max ⁡ ( max ⁡ i ≤ k ≤ j { d [ u k ] } , d i s t ( u 1 , u i ) , d i s t ( u j , u t ) ) \max\Big(\max _{i\le k\le j}\{d[u_k]\},dist(u_1,u_i),dist(u_j,u_t)\Big) max(i≤k≤jmax​{d[uk​]},dist(u1​,ui​),dist(uj​,ut​))

上式可由直徑的最長性簡化為：

max ⁡ ( max ⁡ 1 ≤ k ≤ t { d [ u k ] } , d i s t ( u 1 , u i ) , d i s t ( u j , u t ) ) \max\Big(\max_{1\le k\le t}\{d[u_k]\},dist(u_1,u_i),dist(u_j,u_t)\Big) max(1≤k≤tmax​{d[uk​]},dist(u1​,ui​),dist(uj​,ut​))

max ⁡ 1 ≤ k ≤ t { d [ u k ] } \max_{1\le k\le t}\{d[u_k]\} max1≤k≤t​{d[uk​]}對于 u i , u j u_i,u_j ui​,uj​來說是一個定值。隻需枚舉每個 u i u_i ui​，同時用一個指針，在距離不超過s的前提下，每次沿着直徑向後移動，得到 u j u_j uj​更新答案。時間複雜度 O ( n ) O(n) O(n)

（詳見李煜東《算法競賽進階指南》第364~365頁）

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+10;
struct Edge{
	int v,nx,w;
}e[N<<1];
int n,s,hd[N],tot,fa[N],vis[N],dis[N];
void addedge(int u,int v,int w)
{
	e[tot].v=v;
	e[tot].w=w;
	e[tot].nx=hd[u];
	hd[u]=tot++;
}
void dfs(int u,int f)
{
	fa[u]=f;
	for(int i=hd[u];~i;i=e[i].nx)
	{
		int v=e[i].v;
		if(vis[v]||v==f)continue;
		dis[v]=dis[u]+e[i].w;
		dfs(v,u);
	}
}
int main()
{
	//freopen("in.txt","r",stdin);
	memset(hd,-1,sizeof(hd));
	scanf("%d%d",&n,&s);
	int u,v,w;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		addedge(u,v,w);addedge(v,u,w);
	}
	int l=1,r=1;
	dfs(1,0);
	for(int i=1;i<=n;i++)if(dis[i]>dis[r])r=i;
	l=r;
	dis[r]=0;
	dfs(r,0);
	for(int i=1;i<=n;i++)if(dis[i]>dis[l])l=i;
	int i=l,j=l;
	int ans=0x7fffffff;
	for(;i;i=fa[i])
	{
		while(fa[j]&&dis[i]-dis[fa[j]]<=s)j=fa[j];
		ans=min(ans,max(dis[j],dis[l]-dis[i]));
	}
	for(i=l;i;i=fa[i])vis[i]=1;
	for(i=l;i;i=fa[i])dis[i]=0,dfs(i,fa[i]);
	for(i=1;i<=n;i++)ans=max(ans,dis[i]);
	printf("%d\n",ans);
	return 0;
}
           

總結

此題作為書上例題，難度有以下幾點：

1.讀懂題目。裡面出現了不少定義和公式，大段資訊中隐藏着一些結論。

2.分析性質，得出較為優化的解法。

3.代碼實作，對于“沿着直徑向後移動”，之前沒想到怎麼實作，最後發現其實可以數組實作，說明自己代碼實作能力不足。