『Island 基环树直径』

2023-12-09 13:32:09

<更新提示>

<第一次更新>

<正文>

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

Sample Output

解析

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

大体思路是这样的，对于每一颗基环树，可以先找到基环树的环\(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;

}

<后记>

码农公寓