自动搬运

查看原文

来自洛谷，原作者为

	Mr_cold **

搬运于2025-08-24 21:24:39，当前版本为作者最后更新于2018-08-16 16:37:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

作为一道NOI题，这道题是一道好(难)题，这道题给了一张N点N边的图，让你在图中找一点到图中最远点最近，输出这个距最远点最近的距离，首先问题降低，如果这是一棵树，求一点到最远点的最短距离，那其实就是树的直径的一半，但是这道题是一颗环套树，所以现在分两种情况

1 这个环套树的最长路径不经过环

这种情况是比较简单的，我们首先通过一些手段求出这个环，并记录环的信息，(方法：tarjan，dfs，并查集)；然后枚举每一个环上的点，对这些点下的子树求直径，取这些直径的最大值，记为ans1.

以上操作找环是O(n+m),对所有环上的点求子树是O(n)的，所以这一步总复杂度O(n+m);

时间复杂度的原因：每个点只便利了一次

2 这个环套树的最长路径经过环

这种情况是比较复杂的，O(n * n) 60分算法是枚举环上的断点，是无法AC的，因此需要优化。

规定环上每个点为1--> circle_cnt

A[i]表示(前缀链长度+当前换上节点子树最大深度)

B[i]表示(前缀中两个点子树的最大深度+两点之间的距离)

C[i]表示(后缀链长度+当前换上节点子树最大深度)

D[i]表示(后缀中两个点子树的最大深度+两点之间的距离) 因此当我们枚举到断裂环上i与i+1点之间的边时，

答案为max(max(B[i],D[i]),A[i]+C[i+1]+(1-->circle_cnt点的边权))；

这个式子的含义是 取

max((前缀中的最大直径)，(后缀中的最大直径)，(前缀i与后缀i+1跨过1和circle_cnt点之间的边所组成的直径))

显然的我们要保留这里求出的最小值，因为这里求出的路径是所有路径都有可能，不一定是两点间的最短路，这里我就有疑问，但就像第一个样例，最长的路是3->1->4->2距离为5，事实上有3->1->2->4距离为4的路存在，这样无疑缩短了求的直径。

记这个最小值为ans2.这个步骤复杂度时O(circle_cnt)

最终输出max(ans1,ans2)/2;

How interesting it is!

以上就是主要思路，对于经过环上的路径也可以通过线段树来求，但是没有这种方法更优。 代码如下

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
const int maxn=100000+10;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
int n;
struct Edge{
	int to,from,cost;
}edge[maxn<<1];
int last[maxn<<1],cnt=0;
int huan[maxn],huan_cnt=0,huan_zhi[maxn],fa[maxn],cost[maxn],huan_sign[maxn];
int dfn[maxn],timee=0;
ll dis[maxn];
ll ans=0,ans1=0;
ll A[maxn],B[maxn];
//A[i]表示 前缀中最大的一条链+当前节点树的最大深度 
//B[i]表示前缀中两棵树的最大深度+这两个节点间的距离 
ll C[maxn],D[maxn]; //这是后缀做的
//因此当断换上第i与i+1条边时 ans=max(max(B[i],D[i+1]),A[i]+C[i+1]+1-->cnt的边权和) 
inline int read(){
    int a=1,b=0;char c=getchar();
    while(c>'9'||c<'0'){if(c=='-') a=-1;c=getchar();}
    while(c>='0'&&c<='9'){b=(b<<3)+(b<<1)+c-'0';c=getchar();}
    return a*b;
}
inline void print(ll x){
    if(x<0) x=-x,putchar('-');
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
inline void pre(){
	
}
inline void add(int x,int y,int z){
	edge[++cnt].to=y;
	edge[cnt].cost=z;
	edge[cnt].from=last[x];
	last[x]=cnt;
}
inline void input(){int xx,yy,zz;
	n=read();
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;
		xx=read(),yy=read(),zz=read();
		add(xx,yy,zz);
		add(yy,xx,zz);
	}
}	
inline void dfs(int now){//此处找环并记录 
	dfn[now]=++timee;
	for(int i=last[now];i;i=edge[i].from)
	{
		int to=edge[i].to;
		if(to!=fa[now])
		{
			if(!dfn[to])
			{
				fa[to]=now;
				cost[to]=edge[i].cost;
				dfs(to);
			}
			else if(dfn[to]>dfn[now])
			{
				for(;to!=now;to=fa[to])
				{
					huan_sign[to]=1;
					huan[++huan_cnt]=to;
					huan_zhi[huan_cnt]=cost[to];
				}
				huan_sign[now]=1;
				huan[++huan_cnt]=now;
				huan_zhi[huan_cnt]=edge[i].cost;
			}
			
		}
	}
}
inline void DP(int now,int father){//dis[i]表示i所在的子树上的直径 
	for(int i=last[now];i;i=edge[i].from)
	{
		int to=edge[i].to;
		if(!huan_sign[to]&&to!=father)
		{
			DP(to,now);
			ans=max((ll)dis[now]+dis[to]+edge[i].cost,ans);
			dis[now]=max(dis[now],dis[to]+edge[i].cost);
		}
	}
}
inline void solve(){
	dfs(1);
	for(int i=1;i<=huan_cnt;++i) DP(huan[i],0);
	ll sum=0,maxx=0;
	for(int i=1;i<=huan_cnt;++i)
	{
		sum+=huan_zhi[i-1];
		A[i]=max(A[i-1],dis[huan[i]]+sum);
		B[i]=max(B[i-1],sum+maxx+dis[huan[i]]);
		maxx=max(maxx,dis[huan[i]]-sum);
	}
	sum=maxx=0;
	int tmp=huan_zhi[huan_cnt];huan_zhi[huan_cnt]=0;
	for(int i=huan_cnt;i>=1;--i)
	{
		sum+=huan_zhi[i];
		C[i]=max(C[i+1],dis[huan[i]]+sum);
		D[i]=max(D[i+1],sum+maxx+dis[huan[i]]);
		maxx=max(maxx,dis[huan[i]]-sum);
	}
	ll tep;
	ans1=B[huan_cnt];
	for(int i=1;i<huan_cnt;++i)
	{
		tep=max(B[i],D[i+1]);
		tep=max(tep,A[i]+C[i+1]+tmp);
		ans1=min(tep,ans1);
	}
	ans=max(ans,ans1);
	if(ans&1) print(ans>>1),puts(".5");
	else print(ans>>1),puts(".0");
}
inline void output(){
    
}
int main(){int T;
    T=1;	
    while(T--)
    {	 
        pre();
        input();
        solve();		
        output();
    }
    return  0;
}