BZOJ1791: [Ioi2008]Island 岛屿

时间：2021-12-06 17:51:52

BZOJ1791: [Ioi2008]Island 岛屿

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

BZOJ1791: [Ioi2008]Island 岛屿

题解Here!

现在看到基环树就想哭。。。
我的$NOIP2018DAY2T1$啊。。。
没办法，这已经是过去了。。。
谁让我这个沙茶把自己想出来的正解给$hack$了呢。。。
还智障一样地以为自己的$hack$是对的。。。
不扯了，写题解：
题意就是给出许多基环树，求所有基环树直径的总和。
所以我们只要对每个基环树染个色，然后对每个基环树求直径就好。
但是一个基环树的直径怎么求？
我们发现，基环树的直径有两种情况：
  1. 位于某个子树中且不在环上。即：不经过环上的点。
  2. 部分经过环，且去掉处于环上的边后位于两颗不同的子树内。即：至少经过环上两个点。

所以我们得把环找出来。

同时求出：从每个环上节点出发在不经过环的前提下的最长链。

这里当然借鉴一下网上大佬得拓扑排序找环辣！

于是这个玩意直接丢给拓扑排序就好。

用求树的直径的方法更新答案处理第一种情况。

对于第二种情况，就等价于从环上找出两点$i,j$使得$dp[i]+dis(i,j)+dp[j]$最大。

$dis(i,j)$为两点在环上的最长距离。

$dp[i]$表示以$i$为根的子树内以一个端点为根的最长链。

记得考虑顺时针和逆时针两种走法。

为了快速求出$dp[i]+dis(i,j)+dp[j]$的值，我们破环成链，用单调队列优化。
附带码：
#include<iostream>

#include<algorithm>

#include<cstdio>

#define MAXN 1000010

using namespace std;

int n,c=1,T=0;

int head[MAXN],degree[MAXN],colour[MAXN],que[MAXN<<1];

long long ans=0,dis[MAXN],dp[MAXN],f[MAXN<<1],g[MAXN<<1];

bool vis[MAXN];

struct Edge{

	int next,to,w;

}a[MAXN<<1];

inline int read(){

	int date=0,w=1;char c=0;

	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}

	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}

	return date*w;

}

inline void add(int u,int v,int w){

	a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;

	a[c].to=u;a[c].w=w;a[c].next=head[v];head[v]=c++;

	degree[u]++;degree[v]++;

}

void bfs(int rt){

	int l=1,r=1,u,v;

	que[1]=rt;

	colour[rt]=T;

	while(l<=r){

		u=que[l];

		for(int i=head[u];i;i=a[i].next){

			v=a[i].to;

			if(!colour[v]){

				que[++r]=v;

				colour[v]=T;

			}

		}

		l++;

	}

}

void topsort(){

	int l=1,r=0,u,v;

	for(int i=1;i<=n;i++)if(degree[i]==1)que[++r]=i;

	while(l<=r){

		u=que[l];

		for(int i=head[u];i;i=a[i].next){

			v=a[i].to;

			if(degree[v]>1){

				dis[colour[u]]=max(dis[colour[u]],dp[u]+dp[v]+a[i].w);

				dp[v]=max(dp[v],dp[u]+a[i].w);

				degree[v]--;

				if(degree[v]==1)que[++r]=v;

			}

		}

		l++;

	}

}

void solve(int rt,int colour){

	int u,v,m=0;

	u=rt;

	for(int i=1;i;){

		f[++m]=dp[u];

		degree[u]=1;

		for(i=head[u];i;i=a[i].next){

			v=a[i].to;

			if(degree[v]>1){

				g[m+1]=g[m]+a[i].w;

				u=v;

				break;

			}

		}

	}

	if(m==2){

		int len=0;

		for(int i=head[u];i;i=a[i].next)if(a[i].to==rt)len=max(len,a[i].w);

		dis[colour]=max(dis[colour],dp[rt]+dp[u]+len);

	}

	else{

		int l=1,r=1;

		que[1]=1;

		for(int i=head[u];i;i=a[i].next)if(a[i].to==rt){

			g[m+1]=g[m]+a[i].w;

			break;

		}

		for(int i=1;i<m;i++){

			f[m+i]=f[i];

			g[m+i]=g[m+1]+g[i];

		}

		for(int i=2;i<2*m;i++){

			while(l<=r&&i-que[l]>=m)l++;

			dis[colour]=max(dis[colour],f[i]+f[que[l]]+g[i]-g[que[l]]);

			while(l<=r&&f[que[r]]-g[que[r]]<=f[i]-g[i])r--;

			que[++r]=i;

		}

	}

}

void work(){

	for(int i=1;i<=n;i++)if(degree[i]>1&&!vis[colour[i]]){

		vis[colour[i]]=true;

		solve(i,colour[i]);

		ans+=dis[colour[i]];

	}

	printf("%lld\n",ans);

}

void init(){

	int x,w;

	n=read();

	for(int i=1;i<=n;i++){

		x=read();w=read();

		add(i,x,w);

	}

	for(int i=1;i<=n;i++)if(!colour[i]){T++;bfs(i);}

	topsort();

}

int main(){

	init();

	work();

	return 0;

}

相关文章