Mr_cold
2018-08-16 16:37:49
作为一道NOI题，这道题是一道好(难)题，这道题给了一张N点N边的图，让你在图中找一点到图中最远点最近，输出这个距最远点最近的距离，首先问题降低，如果这是一棵树，求一点到最远点的最短距离，那其实就是树的直径的一半，但是这道题是一颗环套树，所以现在分两种情况
这种情况是比较简单的，我们首先通过一些手段求出这个环，并记录环的信息，(方法：tarjan，dfs，并查集)；然后枚举每一个环上的点，对这些点下的子树求直径，取这些直径的最大值，记为ans1.
以上操作找环是O(n+m),对所有环上的点求子树是O(n)的，所以这一步总复杂度O(n+m);
时间复杂度的原因：每个点只便利了一次
这种情况是比较复杂的，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;
}