记录编号	347431	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]快餐店	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	9.843 s
提交时间	2016-11-13 10:49:07	内存使用	52.82 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef double db;
typedef long long ll;
const int N=500010;
int n,head[N],tail[N],next[N],fa[N],from[N];
struct edge{int f,t,l,o;}w[N];
void add(int f,int num){
	if (!head[f]) head[f]=tail[f]=num;
		else tail[f]=next[tail[f]]=num;
}
db min(db x,db y){return x<y?x:y;}
db max(db x,db y){return x>y?x:y;}
bool OK;
int p[N],m;db len,dis[N],up[N];//存环上的点的序列，个数，及长度 
void dfs(int x){
	for (int i=head[x];i;i=next[i])
	if (w[i].o!=from[x]){
		if (OK) return;
		if (fa[w[i].t]){
			OK=1;dis[x]=w[i].l;p[++m]=x;
			for (int v=x;v!=w[i].t;v=fa[v])
				dis[fa[v]]=dis[v]+up[v],p[++m]=fa[v];
			len=dis[w[i].t];
			return;
		}
		else{
			fa[w[i].t]=x;
			from[w[i].t]=i;
			up[w[i].t]=w[i].l;
			dfs(w[i].t);
		}
	}
}
int P;db h[N],ma[N],ci[N],Max[N],L;//到根深度,子树最大深度、次大深度,子树直径 
void dfs1(int x){
	for (int i=head[x];i;i=next[i])
	if (!fa[w[i].t]){
		fa[w[i].t]=x;
		h[w[i].t]=h[x]+w[i].l;
		dfs1(w[i].t);
		db a=ma[w[i].t]+w[i].l;
		if (a>ma[x]) ci[x]=ma[x],ma[x]=a;else
		if (a>ci[x]) ci[x]=a;
		Max[x]=max(Max[x],Max[w[i].t]);
	}
	Max[x]=max(Max[x],ma[x]+ci[x]);
}
inline db D(int x,int y){
	if (dis[x]<dis[y]) swap(x,y);
	return min(dis[x]-dis[y],len+dis[y]-dis[x]);
}
db A[N],le[N],ri[N];
int sum[N],cnt;
inline int find(db x){
	int l=1,r=cnt;
	while (l!=r){
		int mid=(l+r)>>1;
		if (x>A[mid]) l=mid+1;else r=mid;
	}
	return l;
}
bool check(db x){
	if (x>=L){//说明可行答案在环上 
		cnt=0;
		A[++cnt]=0;A[++cnt]=len;
		for (int i=1;i<=m;i++){
			db R=x-ma[p[i]];
			if (R<0) return 0;
			if (R>=len/2) le[i]=0,ri[i]=len;
				else le[i]=dis[p[i]]-R,ri[i]=dis[p[i]]+R;
			if (le[i]<0) le[i]+=len;
			if (ri[i]>len) ri[i]-=len;
			A[++cnt]=le[i];A[++cnt]=ri[i];
		}
		sort(A+1,A+cnt+1);
		for (int i=0;i<=cnt;i++) sum[i]=0;
		for (int i=1;i<=m;i++){
			int l=find(le[i]),r=find(ri[i]);
			if (le[i]<=ri[i]) sum[l]++,sum[r+1]--;
				else sum[l]++,sum[cnt]--,sum[0]++,sum[r+1]--;
		}
		if (sum[0]>=m) return 1;
		for (int i=1;i<=cnt;i++){
			sum[i]+=sum[i-1];
			if (sum[i]>=m) return 1;
		}
		return 0;
	}
	else{//说明可行答案在链上 
		db le=L;
		for (int i=1;i<=m;i++)
		if (p[i]!=P){
			if (D(P,p[i])+ma[p[i]]>x) return 0;
			le=min(le,x-D(P,p[i])-ma[p[i]]);
		}
		return le+x>=L;
	}
}
db erfen(db l,db r){
	if (r-l<=1e-2) return l;
	db mid=(l+r)/2;
	return check(mid)?erfen(l,mid):erfen(mid,r);
}
int read(){
	int x=0;char ch=getchar();
	while (ch>'9'||ch<'0') ch=getchar();
	while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
int main()
{
	freopen("foodshop.in","r",stdin);
	freopen("foodshop.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		w[i].f=read();w[i].t=read();w[i].l=read();
		w[i+n]=w[i];w[i].o=i+n;w[i+n].o=i;
		swap(w[i].f,w[i].t);
		add(w[i].f,i);add(w[i].t,i+n);
	}
	fa[1]=1;dfs(1);
	memset(fa,0,sizeof fa);
	for (int i=1;i<=m;i++) fa[p[i]]=p[i];
	db l=0;
	for (int i=1;i<=m;i++){
		dfs1(p[i]);l=max(l,Max[p[i]]/2);
		if (L<ma[p[i]]) L=ma[p[i]],P=p[i];
	}
	printf("%.1lf\n",erfen(l,L+len));
	return 0;
}