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
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求环
下面是我的代码
#include<bits/stdc++.h>
#define N 1000005
#define ll long long
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
int n,tot,cnt,tp,fg,num,siz[N],s[N],q[N<<],hd[N];
int cir[N],bl[N],g[N<<],d[N<<],vis[N];
ll len,ans[N],f[N],dis[N<<],dp[N];
struct edge{int v,w,next;}e[N<<];
void adde(int u,int v,int w){
e[++tot].v=v;
e[tot].w=w;
e[tot].next=hd[u];
hd[u]=tot;
}
void dfs1(int u,int fa){
if(vis[u]&&!bl[u]){
cir[++cnt]=u;
int tmp=s[tp];
while(){
bl[tmp]=cnt;--tp;
++siz[cnt];
if(tmp==u)break;
tmp=s[tp];
}
return;
}
if(vis[u])return;
vis[u]=;s[++tp]=u;
int tmp=;
for(int i=hd[u];i;i=e[i].next){
int v=e[i].v;
if(v==fa&&!tmp){tmp=;continue;}
dfs1(v,u);
}
--tp;
}
void getdp(int u,int fa,int id){
ll m1=,m2=,res;
for(int i=hd[u];i;i=e[i].next){
int v=e[i].v;
if(v==fa||bl[v]==id)continue;
getdp(v,u,id);res=e[i].w+dp[v];
dp[u]=max(dp[u],res);
if(res>m1)m2=m1,m1=res;
else if(res>m2)m2=res;
}
ans[id]=max(ans[id],m1+m2);
}
inline ll getd(int i,int j){
return dis[j]-dis[i];
} void solve(int id){
ll &mx=ans[id];int L=siz[id],tid=num;
for(int i=;i<=num;++i)
g[++tid]=g[i],d[tid]=d[i],dis[tid]=dis[i];
int h=,t=;q[]=;mx=max(dp[g[]],mx);
for(int i=;i<tid;++i){
while(h<t&&i-q[h]>=L)h++;
if(i>num&&q[h]>num)break;
if(i>num)f[i]=len-dis[q[h]]+dp[g[q[h]]]+dp[g[i]]+dis[i];
else f[i]=dis[i]-dis[q[h]]+dp[g[q[h]]]+dp[g[i]];
mx=max(f[i],mx);if(i>num)continue;
while(h<=t&&dp[g[q[t]]]+getd(q[t],i)<=dp[g[i]])t--;q[++t]=i;
}
}
void dfs2(int u,int fa,int id){
if(u==cir[id]&&fa){
solve(id);fg=;
return;
}
g[++num]=u;getdp(u,,id);int tmp=;
for(int i=hd[u];i&&!fg;i=e[i].next){
int v=e[i].v;
if(bl[v]!=id)continue;
if(v==fa&&!tmp){tmp=;continue;}
if(v!=cir[id]){
dis[num+]=dis[num]+e[i].w;
d[num+]=e[i].w;
}
else d[]=e[i].w;
len+=e[i].w;dfs2(v,u,id);
}
}
int main(){
scanf("%d",&n);
for(register int i=;i<=n;++i){
int v,w;
scanf("%d%d",&v,&w);
adde(i,v,w);adde(v,i,w);
}
for(register int i=;i<=n;i++)
if(!vis[i])tp=,dfs1(i,);
for(register int i=;i<=cnt;i++){
len=;fg=;num=;dis[]=;
dfs2(cir[i],,i);
}
ll all=;
for(register int i=;i<=cnt;i++)all+=ans[i];
printf("%lld\n",all);
return ;
}
爆栈dfs
然后是网上一个人的代码 用的topsort
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <queue>
#define M 1000005
#define LL long long
using namespace std;
struct edge
{
int y,ne,v;
}e[M*];
int h[M],v[M],c[M],du[M],q[*M],n,m,tot,t;
LL f[M],d[M],a[*M],b[*M];
void Addedge(int x,int y,int v)
{
tot++;
e[tot].y=y;
e[tot].ne=h[x];
h[x]=tot;
e[tot].v=v;
du[x]++;
}
void dfs(int x,int k)
{
v[x]=,c[x]=k;
for (int i=h[x];i;i=e[i].ne)
{
int y=e[i].y;
if (v[y]) continue;
dfs(y,k);
}
}
void Topsort()
{
int l=,r=,y;
for (int i=;i<=n;i++)
if (du[i]==) q[++r]=i;
while (l<=r)
{
int x=q[l];
for (int i=h[x];i;i=e[i].ne)
if (du[y=e[i].y]>)
{
du[y]--;
d[c[x]]=max(d[c[x]],f[x]+f[y]+e[i].v);
f[y]=max(f[y],f[x]+e[i].v);
if (du[y]==) q[++r]=y;
}
l++;
}
}
void Dp(int t,int x)
{
int m=,i,y=x;
do
{
a[++m]=f[y],du[y]=;
for (i=h[y];i;i=e[i].ne)
if (du[e[i].y]>)
{
y=e[i].y;
b[m+]=b[m]+e[i].v;
break;
}
}while (i);
if (m==)
{
int l=;
for (int i=h[y];i;i=e[i].ne)
if (e[i].y==x) l=max(l,e[i].v);
d[t]=max(d[t],f[x]+f[y]+l);
return;
}
for (int i=h[y];i;i=e[i].ne)
if (e[i].y==x)
{
b[m+]=b[m]+e[i].v;
break;
}
for (int i=;i<=m;i++)
{
a[m+i]=a[i];
b[m+i]=b[m+]+b[i];
}
int l,r;
q[l=r=]=;
for (int i=;i<*m;i++)
{
while (l<=r&&i-q[l]>=m)
l++;
d[t]=max(d[t],a[i]+a[q[l]]+b[i]-b[q[l]]);
while (l<=r&&a[q[r]]+b[i]-b[q[r]]<=a[i])
r--;
q[++r]=i;
}
}
int main()
{
scanf("%d",&n);
for (int i=;i<=n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
Addedge(x,i,y);
Addedge(i,x,y);
}
memset(v,,sizeof(v));
t=;
for (int i=;i<=n;i++)
if (!c[i]) dfs(i,++t);
Topsort();
LL ans=0LL;
memset(v,,sizeof(v));
for (int i=;i<=n;i++)
if (du[i]>&&!v[c[i]])
{
v[c[i]]=;
Dp(c[i],i);
ans+=d[c[i]];
}
cout<<ans<<endl;
return ;
}
topsort