时间戳

首页 > 技术文章 > 『Island 基环树直径』

『Island 基环树直径』

Parsnip 2019-03-08 19:17 原文

<更新提示>

<第一次更新>

<正文>

Island(IOI 2008)

Description

你准备浏览一个公园，该公园由 N 个岛屿组成，当地管理部门从每个岛屿 i 出发向另外一个岛屿建了一座长度为 L_i 的桥，不过桥是可以双向行走的。同时，每对岛屿之间都有一艘专用的往来两岛之间的渡船。相对于乘船而言，你更喜欢步行。你希望经过的桥的总长度尽可能长，但受到以下的限制：

  • 可以自行挑选一个岛开始游览。
  • 任何一个岛都不能游览一次以上。
  • 无论任何时间，你都可以由当前所在的岛 S 去另一个从未到过的岛 D。从 S 到 D 有如下方法：
    • 步行：仅当两个岛之间有一座桥时才有可能。对于这种情况，桥的长度会累加到你步行的总距离中。
    • 渡船：你可以选择这种方法，仅当没有任何桥和以前使用过的渡船的组合可以由 SS 走到 D (当检查是否可到达时，你应该考虑所有的路径，包括经过你曾游览过的那些岛)。

注意，你不必游览所有的岛，也可能无法走完所有的桥。

请你编写一个程序，给定 N 座桥以及它们的长度，按照上述的规则，计算你可以走过的桥的长度之和的最大值。

Input Format

第一行包含 N 个整数，即公园内岛屿的数目。

随后的 N 行每一行用来表示一个岛。第 i 行由两个以单空格分隔的整数，表示由岛 i 筑的桥。第一个整数表示桥另一端的岛，第二个整数表示该桥的长度 L_i。你可以假设对于每座桥，其端点总是位于不同的岛上。

Output Format

仅包含一个整数，即可能的最大步行距离。

Sample Input

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

Sample Output

24

解析

很多年前的一道老题了，题意即为：给定基环树森林，求各棵基环树的直径之和。

大体思路是这样的，对于每一颗基环树，可以先找到基环树的环\(loop_{1-k}\)，设以\(loop_i\)为根的树中，以\(loop_i\)为起点的最长链长度为\(deep_i\)，该树中的朴素直径为\(diameter_i\)，那么这一棵基环树的答案一定就是：

\[ans=\max \begin{cases} \max\{diameter_i\} \\ \max\{deep_i+deep_j+path(loop_i,loop_j)\} \end{cases} \]

对于第一个式子，我们直接用树形\(DP\)求树的直径即可。

对于第二个式子，\(deep\)我们显然可以直接\(dfs\)处理，然后我们断环为链并复制一倍，\(path(loop_i,loop_j)\)的长度我们可以改为\(sum_j-sum_i\)，那么就是求

\[\max_{i < j}\{deep_i+deep_j+sum_j-sum_i\} \]

把它当做\(DP\)，枚举\(j\)，单调队列维护\({deep_i-sum_i}\)单调性即可。

然后累加每一棵基环树的答案即可。

我的做题历程和一些我犯过的错误：

  • 单调队列误解，用了单调栈
  • 没有考虑二元环的情况，环上边权选择重复，需要特判
  • 发现做动态规划不能遍历每一种情况，断环为链时需要将链复制放在原链的后面，在做动态规划才能遍历每一种情况，需要顺带改进单调队列，距离当前长度超过\(n\)时弹出队首
  • 发现菊花图的情况很容易被卡，是因为没有判断之间以环上某一个点为根取该树的直径的情况，对于环上每一个点，做一遍\(DP\)找以该节点为根的树的直径，最后以最大值和原答案取\(max\)
  • 没有对每一棵基环树中子树的朴素直径与\(DP\)得到的答案取\(max\)，对于每一棵基环树，应该都取一个\(max\)来累加答案，而非放在最后取

然后就是还有一个点是被卡常的，至于怎么办，我也不知道。

\(Code:\)

#include<bits/stdc++.h>
#define mset(name,val) memset(name,val,sizeof name)
using namespace std;
const int N=1e6+10;
const long long INF=LONG_LONG_MAX;
int n,Last[N*2],t;long long ans,deep[N*2],Link[N*2],sum[2*N],f[N*2],ans_,F[N],D[N];
int dfn[N],a[N*2],loop[N],inloop[N],tot,cnt,fa[N],used[N],vis[N];
struct edge{int ver,next;long long val;}e[N*2];
inline void insert(int x,int y,long long v)
{
	e[++t].val=v;e[t].ver=y;e[t].next=Last[x];Last[x]=t;
}
inline char Getchar()
{ 
    static char buf[100000],*p1=buf,*p2=buf; 
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++; 
}
inline void readll(long long &k)
{
    long long x=0,w=0;char ch;
    while(!isdigit(ch))w|=ch=='-',ch=Getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=Getchar();
    k=(w?-x:x);
}
inline void read(int &k)
{
    int x=0,w=0;char ch;
    while(!isdigit(ch))w|=ch=='-',ch=Getchar();
    while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=Getchar();
    k=(w?-x:x);
}
inline void input(void)
{
	read(n);
	for(register int i=1;i<=n;i++)
	{
		int y;long long v;
		read(y);readll(v);
		insert(i,y,v);
		insert(y,i,v);
	}
}
inline void reset(void)
{
	mset(loop,0);
	mset(inloop,0);
	mset(Link,0);
	mset(deep,0);
	mset(a,0);
	tot=0;cnt=0;ans_=0;
}
inline void find_loop(int u)
{
	dfn[u]=++cnt;
	for(register int i=Last[u];i;i=e[i].next)
	{
		int v=e[i].ver;
		if(v==fa[u])continue;
		if(dfn[v])
		{
			if(dfn[v]<dfn[u])continue;
			loop[++tot]=v,inloop[v]=true;
			for(;v!=u;v=fa[v])
				loop[++tot]=fa[v],inloop[fa[v]]=true;
		}
		else fa[v]=u,find_loop(v);
	}
}
inline long long dfs(int x)
{
	long long res=0;
	used[x]=true;
	for(register int i=Last[x];i;i=e[i].next)
	{
		int y=e[i].ver;
		if(!used[y]&&!inloop[y])
			res=max(res,dfs(y)+e[i].val);
	}
	return res;
}
inline void find_diameter(int x)
{
    vis[x]=true;
    for(register int i=Last[x];i;i=e[i].next)
    {
        int y=e[i].ver;
        if(!vis[y]&&!inloop[y])
        {
            find_diameter(y);
            F[x]=max(F[x],D[x]+D[y]+e[i].val);
            D[x]=max(D[x],D[y]+e[i].val);
        }   
    }
    ans_=max(ans_,F[x]);
}
inline void get_deep(void)
{
	for(register int i=1;i<=tot;i++)
	{
		deep[i]=dfs(loop[i]);
		find_diameter(loop[i]);
	} 
}
inline void init(void)
{
	if(tot>2)
	{
		for(register int i=1;i<=tot;i++)
		{
			for(register int j=Last[loop[i]];j;j=e[j].next)
			{
				if((e[j].ver==loop[i-1]&&i>1)||(e[j].ver==loop[tot]&&i==1))
				{
					Link[i]=e[j].val;
					a[i]=loop[i];
				}
			}
		}
	}
	else
	{
		long long v1=0,v2=0;
		for(register int i=Last[loop[1]];i;i=e[i].next)
		{
			if(e[i].ver==loop[2])
			{
				if(!v1)v1=e[i].val;
				else
				{
					v2=e[i].val;
					break;
				}
			}
		}
		Link[1]=v1;Link[2]=v2;
		a[1]=loop[1];a[2]=loop[2]; 
	}
	for(register int i=tot+1;i<=2*tot;i++)
	{
		Link[i]=Link[i-tot];
		a[i]=a[i-tot];
		deep[i]=deep[i-tot];
	}
	for(register int i=1;i<=tot*2;i++)
		sum[i]=sum[i-1]+Link[i];
}
inline long long calc(int x)
{
	return deep[x]-sum[x];
}
inline long long dp(void)
{
	deque < int > q;long long res=ans_;
	q.push_back(1);res=max(res,deep[1]);
	for(register int j=2;j<=2*tot;j++)
	{
		while(!q.empty()&&j-q.front()>=tot)q.pop_front();
		f[j]=sum[j]+deep[j]+calc(q.front());
		while(!q.empty()&&calc(q.back())<calc(j))q.pop_back();
		q.push_back(j);
		res=max(res,f[j]);
	} 
	return res;
}
int main(void)
{
	input();
	for(int i=1;i<=n;i++)
	{
		if(!dfn[i])
		{
			reset();
			find_loop(i);
			get_deep();
			init();
			ans+=dp();
		}
	}
	printf("%lld\n",ans);
	return 0;
}

<后记>

推荐阅读