bzoj1791: [Ioi2008]Island 岛屿单调队列优化dp

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

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
",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