【Noi2013】快餐店

Source and Judge

Noi2013
bzoj3242

Record

2h

Analysis

第一次写基环树（以前总觉得好麻烦啊不想写什么的……）
这次写是没事干练练码力

如果是一棵树，那么一定是找直径的中点
但在基环树上，直径的许多性质被破坏了，不能直接求图的直径
考虑把基环树转化为树，首先断掉一条边不会使答案更优，而且一定有一条边去掉不会有影响（考虑对最优点到各个点的路径一定是树）

把环拉成序列，然后答案的下界是max 各个树内直径/2，而且断边不会影响这个，先处理好，最后更新ans
然后设我们枚举的断边，右边的节点编号为k=1~cnt-1（从0开始）
然后分情况讨论直径经过环上边的情况，是在断边左边a、右边c或者从右边开始去往左边b
$$
\begin{aligned}
val是挂在这上面的树的最大深度，d是前缀环上距离\
A1(i)=&前缀max的val-d\
B1(i)=&后缀max的val-d\
B2(i)=&后缀max的val+d\
0<i<k,a=&A1(i-1)+d_i+val_i\
0 \leq i<k,b=&B1(k)+d_i+d_{cnt-1}+d_{cnt-1到0}+val_i\
k \leq i<cnt,c=&B2(i+1)-d_i+val_i\
ans=&min(ans,max(a,b,c))
\end{aligned}
$$

那么显然可以 O(n) 做了

//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

namespace mine
{
	typedef long long ll;
	const ll INF=1ll<<60;
	// #define pr pair<int,int>
	// #define FR first
	// #define SE second
	// #define MP make_pair

	const int MAX_N=1e5+10;
	int hou[MAX_N];bool v[MAX_N];
	struct Edge{int y,c,g;}e[MAX_N*2];
	int ln=0;void ins(int x,int y,int c) {e[++ln]=(Edge){y,c,hou[x]};hou[x]=ln;}

	stack<int> sta;bool in[MAX_N];
	vector<int> id;
	bool dfs(int x,int fa)
	{
		if(in[x])
		{
			while(1)
			{
				int now=sta.top();sta.pop();
				id.push_back(now);v[now]=1;
				if(now==x) break;
			}
			return 1;
		}
		in[x]=1,sta.push(x);
		for(int k=hou[x];k>0;k=e[k].g)
		{
			int y=e[k].y;if(y==fa) continue;
			if(dfs(y,x)) return 1;
		}
		in[x]=0;sta.pop();
		return 0;
	}

	ll f[MAX_N],zjmx=0;
	void getzj(int x,int fa)
	{
		for(int k=hou[x];k>0;k=e[k].g)
		{
			int y=e[k].y;if(y==fa or v[y]) continue;
			getzj(y,x);zjmx=max(zjmx,f[x]+f[y]+e[k].c);
			f[x]=max(f[x],f[y]+e[k].c);
		}
	}

	ll d[MAX_N],val[MAX_N];
	ll A1[MAX_N],B1[MAX_N],B2[MAX_N];
	struct Nod{ll d;int p;}tmp[MAX_N];bool cmp(Nod a,Nod b){return a.d>b.d;}
	void main()
	{
		int n;scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			int a,b,c;scanf("%d%d%d",&a,&b,&c);
			ins(a,b,c);ins(b,a,c);
		}
		dfs(1,0);int cnt=id.size();
		for(int i=0;i<cnt;i++)
		{
			if(i!=0) for(int k=hou[id[i]];k>0;k=e[k].g) if(e[k].y==id[i-1]) d[i]=e[k].c;
			d[i]+=d[i==0?0:i-1];getzj(id[i],0);val[i]=f[id[i]];
		}
		for(int k=hou[id[0]];k>0;k=e[k].g) if(e[k].y==id[cnt-1]) d[cnt]=e[k].c;

		A1[0]=val[0]-d[0];for(int i=1;i<cnt;i++) A1[i]=max(A1[i-1],val[i]-d[i]);
		B1[cnt]=B2[cnt]=-INF;
		for(int i=cnt-1;i>=0;i--) B1[i]=max(B1[i+1],val[i]-d[i]),B2[i]=max(B2[i+1],val[i]+d[i]);

		for(int i=0;i<=cnt-2;i++) tmp[i]=(Nod){B2[i+1]-d[i]+val[i],i};
		sort(tmp,tmp+cnt-1,cmp);
		ll ans=INF,A=-INF,B=d[0]+val[0];
		for(int k=1,now=0;k<cnt;k++)
		{
			ll a=A,b=B1[k]+d[cnt-1]+d[cnt]+B;
			while(now!=cnt-1 and tmp[now].p<k) now++;
			ll c=(now==cnt-1?-INF:tmp[now].d);
			ans=min(ans,max(a,max(b,c)));
			A=max(A,A1[k-1]+d[k]+val[k]);
			B=max(B,d[k]+val[k]);
		}
		ans=min(ans,A);//断0->cnt-1
		printf("%.1lf",max(zjmx,ans)/2.0);
	}
};
int main()
{
	srand(time(0));
	mine::main();
}