P4381 [IOI2008]Island

題意：

給你一棵基環樹森林，求出基環樹的直徑之和.

題解：

對于基環樹,我們將環看作根,那么直徑有兩種情況::

1.不經過環,也就是環上某個點的子樹內部,對于這種情況,直接在子樹內部處理直徑,更新答案即可;

2.經過環,答案就是i的子樹內長度+j的子樹內長度+i和j之間的距離，我們預處理出環上每個點到其子樹上的最長距離,在預處理一個環上前綴和,ans=max{sondis[i]+sondis[j]+sumcircle[i]-sumcircle[j]},更新答案即可.
sondis[i]記錄環上的第i個點到其子樹的最遠距離;
sumcircle[]記錄環上距離前綴和;
sumcircle[i]-sumcircle[j]即為i和j的距離

代碼：

#include<cstdio> #include<iostream> #include<algorithm> #define ll long long using namespace std; const int N=1e6+3; int to[N<<1],nex[N<<1],head[N],w[N<<1],tt; int c[N];//記錄當前節點屬于第幾棵基環樹; int dg[N];//記錄度數; int q[N<<1];//數組模擬隊列; ll d[N];//d[i]記錄第i棵樹上的直徑; ll f[N];//f[i]記錄從i點向兒子方向上所可以走的最長距離; ll sumcircle[N<<1];//環上距離前綴和; ll sondis[N<<1];//sondis[i]記錄環上的第i個點到其子樹的最遠距離; int cnt,n; bool vis[N];//標記當前基環樹是否已解決過; inline void add(int x,int y,int W){to[++tt]=y,w[tt]=W,nex[tt]=head[x],head[x]=tt;return ; } inline void bfs(int p,int t){int l=0,r=1;q[1]=p,c[p]=t;//廣搜預處理每一個點所屬基環樹的編號;while(l<r){++l;int x=q[l];for(int i=head[x],v;i;i=nex[i]){v=to[i];if(!c[v]){q[++r]=v;c[v]=t;}}}return ; } inline void top_sort(){//拓撲排序求不經過環的直徑,從葉子節點向根(環)遍歷;int l=0,r=0;for(int i=1;i<=n;++i)if(dg[i]==1)q[++r]=i;//將所有度數為1的點先加入隊列中(即葉子結點);while(l<r){++l;int x=q[l];for(int i=head[x],v;i;i=nex[i]){v=to[i];if(dg[v]>1){//此時v在以環為根的樹上是其實是x的父親;d[c[x]]=max(d[c[x]],f[x]+f[v]+w[i]);//更新當前基環樹上的答案;f[v]=max(f[v],f[x]+w[i]);//更新父節點可以到達的最遠節點;if(--dg[v]==1)q[++r]=v;//若當前度數現在變為1,入隊;}}}return ; } inline void work(int t,int x){int tot=0,l,r,v=x,u,i;//在拓撲排序后已經將非環上的邊遍歷完了,環上的邊和點均還未遍歷,且度數為2,將x看做環上的起點,v看做終點;do{dg[v]=1;sondis[++tot]=f[v];//將當前點度數記為1,防止反向遍歷,同時記錄第tot號環上節點到子樹上的最短距離;for(i=head[v];i;i=nex[i]){u=to[i];if(dg[u]>1){//環上的點度數均大于1,所以度數大于1的點即是環上的點;v=u;//更新終點;sumcircle[tot+1]=sumcircle[tot]+w[i];//處理環上距離前綴和;break;//保證向一邊枚舉,所以找到一個點就break;}}}while(i);if(tot==2){//特殊處理二元環;int len=0;for(i=head[v];i;i=nex[i]){u=to[i];if(u==x){len=max(len,w[i]);//找出兩個點之間較大的邊; }}d[t]=max(d[t],(ll)len+f[x]+f[v]);//更新答案;return ;}for(int i=head[v],u;i;i=nex[i]){u=to[i];if(u==x){sumcircle[tot+1]=sumcircle[tot]+w[i];//將起點和終點的距離處理出來;break;}}for(i=1;i<tot;i++)//斷環為鏈,再復制一遍數組;{sondis[tot+i]=sondis[i];sumcircle[tot+i]=sumcircle[tot+1]+sumcircle[i];}q[1]=1;l=r=1;for(int i=2;i<tot<<1;++i){while(l<=r&&i-q[l]>=tot)++l;//將超出環長度的部分彈出;d[t]=max(d[t],sondis[q[l]]+sondis[i]+sumcircle[i]-sumcircle[q[l]]);while(l<=r&&sondis[q[r]]+sumcircle[i]-sumcircle[q[r]]<=sondis[i])--r;//將隊尾答案不夠優秀的部分彈出;q[++r]=i;//入隊;}return ; } int main(){cin>>n;int x,W;for(int i=1;i<=n;++i){scanf("%d%d",&x,&W);add(x,i,W);add(i,x,W);++dg[x];++dg[i];}for(int i=1;i<=n;++i)if(!c[i])bfs(i,++cnt);//預處理;top_sort();//拓撲排序求直徑;ll ans=0;for(int i=1;i<=n;++i)if(dg[i]>1&&!vis[c[i]]){//如果當前基環樹未被處理,并且當前點是環上點,就處理;vis[c[i]]=true;work(c[i],i);ans+=d[c[i]];//累加答案;}cout<<ans<<'\n';return 0; }

總結

以上是生活随笔為你收集整理的P4381 [IOI2008]Island的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。