1791: [Ioi2008]Island 島嶼

Time Limit:?20 Sec??Memory Limit:?162 MB
Submit:?1826??Solved:?405
[Submit][Status][Discuss]

Description

你將要游覽一個有N個島嶼的公園。從每一個島i出發，只建造一座橋。橋的長度以Li表示。公園內總共有N座橋。盡管每座橋由一個島連到另一個島，但每座橋均可以雙向行走。同時，每一對這樣的島嶼，都有一艘專用的往來兩島之間的渡船。 相對于乘船而言，你更喜歡步行。你希望所經過的橋的總長度盡可能的長，但受到以下的限制。 ? 可以自行挑選一個島開始游覽。 ? 任何一個島都不能游覽一次以上。 ? 無論任何時間你都可以由你現在所在的島S去另一個你從未到過的島D。由S到D可以有以下方法： o 步行：僅當兩個島之間有一座橋時才有可能。對于這種情況，橋的長度會累加到你步行的總距離；或者 o 渡船：你可以選擇這種方法，僅當沒有任何橋和/或以前使用過的渡船的組合可以由S走到D（當檢查是否可到達時，你應該考慮所有的路徑，包括經過你曾游覽過的那些島）。 注意，你不必游覽所有的島，也可能無法走完所有的橋。 任務 編寫一個程序，給定N座橋以及它們的長度，按照上述的規則，計算你可以走過的橋的最大長度。 限制 2 <= N <= 1,000,000 公園內的島嶼數目。 1<= Li <= 100,000,000 橋i的長度。

Input

? 第一行包含N個整數，即公園內島嶼的數目。島嶼由1到N編號。 ? 隨后的N行每一行用來表示一個島。第i 行由兩個以單空格分隔的整數，表示由島i筑的橋。第一個整數表示橋另一端的島，第二個整數表示該橋的長度Li。你可以假設對於每座橋，其端點總是位于不同的島上。

Output

你的程序必須向標準輸出寫出包含一個整數的單一行，即可能的最大步行距離。 注1：對某些測試，答案可能無法放進32-bit整數，你要取得這道題的滿分，可能需要用Pascal的int64或C/C++的long long類型。 注2：在比賽環境運行Pascal程序，由標準輸入讀入64-bit數據比32-bit數據要慢得多，即使被讀取的數據可以32-bit表示。我們建議把輸入數據讀入到32-bit數據類型。 評分 N不會超過4,000。

Sample Input

7
3 8
7 2
4 2
1 4
1 9
3 4
2 3

Sample Output

24

HINT

Source

題目理解一下就變成了求多棵基環外向樹直徑的和

對于任意一棵基環外向樹，可以先對于環上每個點i做一個樹形dp求出i向外延伸的最大距離

如果直徑不經過環 那么在做樹形dp的時候就可以找出來

如果經過環，那么在環上dp：

把每個點向外延伸的最大距離當成點權，問題即轉化為求環上兩點i，j 要求dis（i，j）+v[i]+v[j]最大

把無向環看作有向環，即把序列倍增一次補在后面，這樣即可實現單方向轉移

單調隊列維護轉移，在轉移長度達到環長的時候head++

http://blog.csdn.net/vmurder/article/details/38940815

?

我寫錯了很多地方：

1.維護單調隊列單調性時求兩點距離錯了

2.先沒想到直徑可以不經過環

3.數組爆掉

4.爆棧

前面3點在經過3h的調試之后更正了

第四點無法優化，因為bzoj好像不讓自己擴棧？

?

爆棧這個問題，其實可以避免

我是dfs找環 再dfs環求dp? （不炸成瓜皮才怪）

看了看網上更優的方法，可以先求每個聯通塊，然后對聯通塊topsort，topsort的時候順便轉移dp

感覺自己宛如一個zz，又忘記了topsort求環

下面是我的代碼? 1 #include<bits/stdc++.h> 2 #define N 1000005 3 #define ll long long 4 #pragma comment(linker, "/STACK:102400000,102400000") 5 using namespace std; 6 int n,tot,cnt,tp,fg,num,siz[N],s[N],q[N<<1],hd[N]; 7 int cir[N],bl[N],g[N<<1],d[N<<1],vis[N]; 8 ll len,ans[N],f[N],dis[N<<1],dp[N]; 9 struct edge{int v,w,next;}e[N<<1]; 10 void adde(int u,int v,int w){ 11 e[++tot].v=v; 12 e[tot].w=w; 13 e[tot].next=hd[u]; 14 hd[u]=tot; 15 } 16 void dfs1(int u,int fa){ 17 if(vis[u]&&!bl[u]){ 18 cir[++cnt]=u; 19 int tmp=s[tp]; 20 while(1){ 21 bl[tmp]=cnt;--tp; 22 ++siz[cnt]; 23 if(tmp==u)break; 24 tmp=s[tp]; 25 } 26 return; 27 } 28 if(vis[u])return; 29 vis[u]=1;s[++tp]=u; 30 int tmp=0; 31 for(int i=hd[u];i;i=e[i].next){ 32 int v=e[i].v; 33 if(v==fa&&!tmp){tmp=1;continue;} 34 dfs1(v,u); 35 } 36 --tp; 37 } 38 void getdp(int u,int fa,int id){ 39 ll m1=0,m2=0,res; 40 for(int i=hd[u];i;i=e[i].next){ 41 int v=e[i].v; 42 if(v==fa||bl[v]==id)continue; 43 getdp(v,u,id);res=e[i].w+dp[v]; 44 dp[u]=max(dp[u],res); 45 if(res>m1)m2=m1,m1=res; 46 else if(res>m2)m2=res; 47 } 48 ans[id]=max(ans[id],m1+m2); 49 } 50 inline ll getd(int i,int j){ 51 return dis[j]-dis[i]; 52 } 53 54 void solve(int id){ 55 ll &mx=ans[id];int L=siz[id],tid=num; 56 for(int i=1;i<=num;++i) 57 g[++tid]=g[i],d[tid]=d[i],dis[tid]=dis[i]; 58 int h=1,t=1;q[1]=1;mx=max(dp[g[1]],mx); 59 for(int i=2;i<tid;++i){ 60 while(h<t&&i-q[h]>=L)h++; 61 if(i>num&&q[h]>num)break; 62 if(i>num)f[i]=len-dis[q[h]]+dp[g[q[h]]]+dp[g[i]]+dis[i]; 63 else f[i]=dis[i]-dis[q[h]]+dp[g[q[h]]]+dp[g[i]]; 64 mx=max(f[i],mx);if(i>num)continue; 65 while(h<=t&&dp[g[q[t]]]+getd(q[t],i)<=dp[g[i]])t--;q[++t]=i; 66 } 67 } 68 void dfs2(int u,int fa,int id){ 69 if(u==cir[id]&&fa){ 70 solve(id);fg=1; 71 return; 72 } 73 g[++num]=u;getdp(u,0,id);int tmp=0; 74 for(int i=hd[u];i&&!fg;i=e[i].next){ 75 int v=e[i].v; 76 if(bl[v]!=id)continue; 77 if(v==fa&&!tmp){tmp=1;continue;} 78 if(v!=cir[id]){ 79 dis[num+1]=dis[num]+e[i].w; 80 d[num+1]=e[i].w; 81 } 82 else d[1]=e[i].w; 83 len+=e[i].w;dfs2(v,u,id); 84 } 85 } 86 int main(){ 87 scanf("%d",&n); 88 for(register int i=1;i<=n;++i){ 89 int v,w; 90 scanf("%d%d",&v,&w); 91 adde(i,v,w);adde(v,i,w); 92 } 93 for(register int i=1;i<=n;i++) 94 if(!vis[i])tp=0,dfs1(i,0); 95 for(register int i=1;i<=cnt;i++){ 96 len=0;fg=0;num=0;dis[1]=0; 97 dfs2(cir[i],0,i); 98 } 99 ll all=0; 100 for(register int i=1;i<=cnt;i++)all+=ans[i]; 101 printf("%lld\n",all); 102 return 0; 103 } 爆棧dfs

?

然后是網上一個人的代碼? 用的topsort

1 #include <iostream> 2 #include <algorithm> 3 #include <cstdio> 4 #include <cstdlib> 5 #include <cstring> 6 #include <queue> 7 #define M 1000005 8 #define LL long long 9 using namespace std; 10 struct edge 11 { 12 int y,ne,v; 13 }e[M*2]; 14 int h[M],v[M],c[M],du[M],q[2*M],n,m,tot,t; 15 LL f[M],d[M],a[2*M],b[2*M]; 16 void Addedge(int x,int y,int v) 17 { 18 tot++; 19 e[tot].y=y; 20 e[tot].ne=h[x]; 21 h[x]=tot; 22 e[tot].v=v; 23 du[x]++; 24 } 25 void dfs(int x,int k) 26 { 27 v[x]=1,c[x]=k; 28 for (int i=h[x];i;i=e[i].ne) 29 { 30 int y=e[i].y; 31 if (v[y]) continue; 32 dfs(y,k); 33 } 34 } 35 void Topsort() 36 { 37 int l=1,r=0,y; 38 for (int i=1;i<=n;i++) 39 if (du[i]==1) q[++r]=i; 40 while (l<=r) 41 { 42 int x=q[l]; 43 for (int i=h[x];i;i=e[i].ne) 44 if (du[y=e[i].y]>1) 45 { 46 du[y]--; 47 d[c[x]]=max(d[c[x]],f[x]+f[y]+e[i].v); 48 f[y]=max(f[y],f[x]+e[i].v); 49 if (du[y]==1) q[++r]=y; 50 } 51 l++; 52 } 53 } 54 void Dp(int t,int x) 55 { 56 int m=0,i,y=x; 57 do 58 { 59 a[++m]=f[y],du[y]=1; 60 for (i=h[y];i;i=e[i].ne) 61 if (du[e[i].y]>1) 62 { 63 y=e[i].y; 64 b[m+1]=b[m]+e[i].v; 65 break; 66 } 67 }while (i); 68 if (m==2) 69 { 70 int l=0; 71 for (int i=h[y];i;i=e[i].ne) 72 if (e[i].y==x) l=max(l,e[i].v); 73 d[t]=max(d[t],f[x]+f[y]+l); 74 return; 75 } 76 for (int i=h[y];i;i=e[i].ne) 77 if (e[i].y==x) 78 { 79 b[m+1]=b[m]+e[i].v; 80 break; 81 } 82 for (int i=1;i<=m;i++) 83 { 84 a[m+i]=a[i]; 85 b[m+i]=b[m+1]+b[i]; 86 } 87 int l,r; 88 q[l=r=1]=1; 89 for (int i=2;i<2*m;i++) 90 { 91 while (l<=r&&i-q[l]>=m) 92 l++; 93 d[t]=max(d[t],a[i]+a[q[l]]+b[i]-b[q[l]]); 94 while (l<=r&&a[q[r]]+b[i]-b[q[r]]<=a[i]) 95 r--; 96 q[++r]=i; 97 } 98 } 99 int main() 100 { 101 scanf("%d",&n); 102 for (int i=1;i<=n;i++) 103 { 104 int x,y; 105 scanf("%d%d",&x,&y); 106 Addedge(x,i,y); 107 Addedge(i,x,y); 108 } 109 memset(v,0,sizeof(v)); 110 t=0; 111 for (int i=1;i<=n;i++) 112 if (!c[i]) dfs(i,++t); 113 Topsort(); 114 LL ans=0LL; 115 memset(v,0,sizeof(v)); 116 for (int i=1;i<=n;i++) 117 if (du[i]>1&&!v[c[i]]) 118 { 119 v[c[i]]=1; 120 Dp(c[i],i); 121 ans+=d[c[i]]; 122 } 123 cout<<ans<<endl; 124 return 0; 125 } topsort

?

?

轉載于:https://www.cnblogs.com/wsy01/p/8135697.html

總結

以上是生活随笔為你收集整理的bzoj1791: [Ioi2008]Island 岛屿 单调队列优化dp的全部內容，希望文章能夠幫你解決所遇到的問題。

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