正題

題目鏈接:https://www.luogu.com.cn/problem/P5895

---

題目大意

$n$個(gè)點(diǎn)的一個(gè)森林，加入若干條長(zhǎng)度為$L$的邊使它變成一個(gè)樹(shù)，求這棵樹(shù)的最小直徑。

---

解題思路

顯然最優(yōu)情況一定是以某個(gè)節(jié)點(diǎn)作為中間展開(kāi)的一個(gè)菊花圖（每棵樹(shù)看做一個(gè)點(diǎn)）。

而且每個(gè)被連接的節(jié)點(diǎn)一定是樹(shù)上的一個(gè)節(jié)點(diǎn)滿足離它最遠(yuǎn)的節(jié)點(diǎn)最近。我們的定義這個(gè)距離為這棵樹(shù)的半徑$r$。

那么答案分為三種情況（以下的$r$按照大小排序）

某棵樹(shù)的直徑

$r_1+r_2+l$（$r_1$的樹(shù)作為中心，$r_2$連接這個(gè)點(diǎn)）

$r_2+r_3+l?2$（$r_1$的樹(shù)作為中心，直徑跨越這個(gè)中間點(diǎn)）

然后樹(shù)形$dp$求解即可，時(shí)間復(fù)雜度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; struct node{int to,next,w; }a[N*2]; int l,n,m,ans,tot,cnt,tmp,r[N],g[N],f[N],ls[N],fr[N]; bool v[N]; void addl(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=w;return; } void dfs(int x,int fa){v[x]=1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;dfs(y,x);if(f[y]+a[i].w>f[x])g[x]=f[x],f[x]=f[y]+a[i].w,fr[x]=y;else if(f[y]+a[i].w>g[x])g[x]=f[y]+a[i].w;}ans=max(ans,f[x]+g[x]);return; } void dp(int x,int fa){tmp=min(tmp,f[x]);for(int i=ls[x];i;i=a[i].next){int y=a[i].to,w;if(y==fa)continue;if(y==fr[x])w=g[x]+a[i].w;else w=f[x]+a[i].w;if(w>f[y])g[y]=f[y],f[y]=w,fr[y]=x;else if(w>g[y])g[y]=w;dp(y,x);}return; } int main() {scanf("%d%d%d",&n,&m,&l);for(int i=1;i<=m;i++){ int x,y,w;scanf("%d%d%d",&x,&y,&w);x++;y++;addl(x,y,w);addl(y,x,w);}for(int i=1;i<=n;i++){if(v[i])continue;dfs(i,0);tmp=2147483647;dp(i,0);r[++cnt]=tmp;}sort(r+1,r+1+cnt);if(cnt>=2)ans=max(ans,r[cnt]+r[cnt-1]+l);if(cnt>=3)ans=max(ans,r[cnt-1]+r[cnt-2]+l*2);printf("%d\n",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的P5895-[IOI2013]dreaming梦想【树的直径,结论】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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