正題

評測記錄:https://www.luogu.org/recordnew/lists?uid=52918&pid=P4381

---

題目大意

有n個島，n條無向邊(保證每個島都有邊連到)。走過的路和島不可以重走，可以坐船。
坐船要求之前沒有任何使用過的船加上道路可以到達(dá)那個點才可以坐船。

求最長可以走多遠(yuǎn)。

---

解題思路

首先這是一棵基環(huán)樹森林，根據(jù)乘船的規(guī)定其實就是每棵基環(huán)樹只可以走一次。這時候我們就可以發(fā)現(xiàn)答案就是每棵基環(huán)樹的直徑之和。然后我們考慮如何計算直徑。

將環(huán)看作根。我們發(fā)現(xiàn)答案只有兩種可能

經(jīng)過根

不經(jīng)過根

我們考慮不經(jīng)過根的，計算出$f_x$($f_x$表示x子樹中離x最遠(yuǎn)的點的距離)，然后用求樹的直徑的方法求出根以下每棵子樹的直徑并記錄。然后我們計算經(jīng)過根的。
假設(shè)環(huán)的節(jié)點為$s$集合，那么答案就是$max(f_{s_i}+f_{s_j}+di{s}_{i～j})$
dis表示環(huán)上i到j(luò)的最遠(yuǎn)距離。
我們可以通過單調(diào)隊列dp計算出答案。

---

code

#include<cstdio> #include<algorithm> #include<queue> #include<iostream> #define N 1000010 #define lls long long using namespace std; struct node{int to,next,w; }a[2*N]; int n,x,y,tot,t; lls ls[N],in[N],cr[2*N],v[N],k[N],f[N],d[N],dis[2*N],ans,q[2*N]; void addl(int x,int y,int w)//加邊 {a[++tot].to=y;a[tot].w=w;a[tot].next=ls[x];ls[x]=tot;in[y]++; } void dfs(int now,int k){v[now]=k;for (int i=ls[now];i;i=a[i].next){int y=a[i].to;if(!v[y]) dfs(y,k);} }//標(biāo)記聯(lián)通塊 void topsort(){int l=0,r=0;for (int i=1;i<=n;i++) if(in[i]==1) q[++r]=i;while(l<r) {int now=q[++l];for (int i=ls[now];i;i=a[i].next){int y=a[i].to;if(in[y]>1){in[y]--;d[v[now]]=max(d[v[now]],f[now]+f[y]+a[i].w);f[y]=max(f[y],f[now]+a[i].w);if(in[y]==1) q[++r]=y;}}} }//拓?fù)渑判蚯蟓h(huán) void dp(int t,int x){int m=0,y=x,i;do{cr[++m]=f[y];in[y]=1;for(i=ls[y];i;i=a[i].next){if(in[a[i].to]>1){dis[m+1]=dis[m]+a[i].w;y=a[i].to;break;}}}while(i);//預(yù)處理環(huán)的數(shù)據(jù)if(m==2){int l=0;for (int i=ls[y];i;i=a[i].next) if(a[i].to==x) l=max(l,a[i].w);d[t]=max(d[t],f[x]+f[y]+l);return;}//特批for(int i=ls[y];i;i=a[i].next){if(a[i].to==x) {dis[m+1]=dis[m]+a[i].w;break;}}//連接首尾for (int i=1;i<=m;i++){cr[i+m]=cr[i];dis[m+i]=dis[m+1]+dis[i];}//復(fù)制一份放在后面int l=1,r=0;q[++r]=1;for (int i=2;i<2*m;i++){while(l<=r&&i-q[l]>=m)l++;d[t]=max(dis[i]-dis[q[l]]+cr[i]+cr[q[l]],d[t]);while(l<=r&&cr[q[r]]+dis[i]-dis[q[r]]<=cr[i])r--;q[++r]=i;}//單調(diào)隊列dp } int main(){scanf("%d",&n);for (int i=1;i<=n;i++){scanf("%d%d",&x,&y);addl(i,x,y);addl(x,i,y);}for (int i=1;i<=n;i++) if (!v[i]) dfs(i,++t);topsort();for (int i=1;i<=n;i++){if(in[i]>1&&!k[v[i]]) {k[v[i]]=1;dp(v[i],i);ans+=d[v[i]];}}printf("%lld",ans); }

總結(jié)

以上是生活随笔為你收集整理的bzoj1791,P4381-[IOI2008]Island【基环树,树形dp,单调队列dp,树的直径】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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