bzoj千题计划114:bzoj1791: [Ioi2008]Island 岛屿

http://www.lydsy.com/JudgeOnline/problem.php?id=1791

就是求所有基环树的直径之和

加手工栈

#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm> using namespace std; #define N 1000001 typedef long long LL; int tot=,front[N],to[N<<],nxt[N<<],l[N<<]; bool vis[N];
int fa[N],dep[N]; int cir[N<<],val[N],cnt; bool inc[N]; LL dp[N],len[N<<],maxn,ans; int h,t,q[N<<]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} void add(int u,int v,int w)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; l[tot]=w;
to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; l[tot]=w;
} int lev2; int st_i2[N],st_x2[N],st_y2[N],st_t2[N]; #define i st_i2[lev2]
#define y st_y2[lev2]
#define x st_x2[lev2]
#define t st_t2[lev2] void dfs(int s,int sf)
{
lev2=;
st_x2[]=s;
start:;
for(i=front[x];i;i=nxt[i])
{
t=to[i];
if(t==y || inc[t]) continue;
st_x2[lev2+]=t;
st_y2[lev2+]=x;
lev2++;
goto start;
end:;
maxn=max(maxn,dp[x]+dp[t]+l[i]);
dp[x]=max(dp[x],dp[t]+l[i]);
}
lev2--;
if(lev2) goto end;
} #undef i
#undef y
#undef t
#undef x int lev; int st_i[N],st_x[N],st_y[N],st_t[N]; #define i st_i[lev]
#define y st_y[lev]
#define x st_x[lev]
#define t st_t[lev] void findcircle(int s)
{
lev=;
st_x[lev]=s;
dep[s]=;
start:;
vis[x]=true;
for(i=front[x];i;i=nxt[i])
{
t=to[i];
if(!vis[t])
{
fa[t]=x;
val[x]=l[i];
dep[t]=dep[x]+;
st_x[lev+]=t;
st_y[lev+]=i;
lev++;
goto start;
end:;
}
else if(i!=(y^))
{
cnt=dep[x]-dep[t]+;
int now=x;
val[x]=l[i];
while(dep[now]>=dep[t])
{
inc[now]=true;
len[cnt]=val[now];
cir[cnt--]=now;
now=fa[now];
}
cnt=dep[x]-dep[t]+;
int nn=cnt;
for(int j=;j<=cnt;++j) cir[++nn]=cir[j],len[nn]=len[j];
for(int j=;j<=nn;++j) len[j]+=len[j-];
for(int j=;j<=cnt;++j) dfs(cir[j],);
h=t=;
for(int j=;j<=nn;++j)
{
while(h<t && q[h]<=j-cnt) h++;
if(h<t) maxn=max(maxn,dp[cir[q[h]]]+dp[cir[j]]+len[j-]-len[q[h]-]);
while(h<t && dp[cir[j]]-len[j-]>dp[cir[q[t-]]]-len[q[t-]-]) t--;
q[t++]=j;
}
} }
lev--;
if(lev) goto end;
} #undef i
#undef y
#undef t
#undef x int main()
{
// freopen("isl.in","r",stdin);
// freopen("isl.out","w",stdout);
int n;
read(n);
int x,y;
for(int i=;i<=n;++i)
{
read(x); read(y);
add(i,x,y);
}
for(int i=;i<=n;++i)
if(!vis[i])
{
maxn=;
findcircle(i);
ans+=maxn;
}
cout<<ans;
}

1791: [Ioi2008]Island 岛屿

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 1795  Solved: 400
[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

bzoj千题计划114:bzoj1791: [Ioi2008]Island 岛屿

Source

上一篇:BZOJ1791: [Ioi2008]Island 岛屿


下一篇:C++ Primer 笔记——数组