记录编号	286457	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2013]快餐店	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	0.823 s
提交时间	2016-07-31 09:22:04	内存使用	9.30 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const int N=100010;
int n,cnt,fir[N],nxt[N<<1],to[N<<1];
LL val[N<<1],dis[N],ans,sum,Mx;
LL u1[N],v1[N],b[N],c[N];
LL u2[N],v2[N];
bool ring[N];
void addedge(int a,int b,int v){
	nxt[++cnt]=fir[a];
	val[cnt]=v;
	fir[a]=cnt;
	to[cnt]=b;
}

int ID[N],tot;
int st[N],top;
int pre[N];
void DFS(int x){
	ID[x]=++tot;
	for(int i=fir[x],y;i;i=nxt[i])
		if((y=to[i])!=pre[x]){
			if(!ID[y]){
				pre[y]=x;
				c[y]=val[i];
				DFS(y);
			}
			else if(ID[y]>ID[x]){
					 while(x!=y){
						st[++top]=y;
						b[top]=c[y];
						ring[y]=true;
						y=pre[y];
					 }
					 st[++top]=x;
					 b[top]=val[i];
					 ring[x]=true;
					 return;
				 }
		}
}

void DP(int x,int fa){
	for(int i=fir[x];i;i=nxt[i])
		if(to[i]!=fa&&!ring[to[i]]){
			DP(to[i],x);
			ans=max(ans,dis[x]+dis[to[i]]+val[i]);
			dis[x]=max(dis[x],dis[to[i]]+val[i]);
		}
}

int main(){
	freopen("foodshop.in","r",stdin);
	freopen("foodshop.out","w",stdout);
	scanf("%d",&n);
	for(int i=1,x,y,v;i<=n;i++){
		scanf("%d%d%d",&x,&y,&v);
		addedge(x,y,v);addedge(y,x,v);
	}
	DFS(1);
	for(int i=1;i<=top;i++)DP(st[i],0);
	
	for(int i=1;i<=top;i++){
		sum+=b[i-1];
		u1[i]=max(u1[i-1],sum+dis[st[i]]);
		v1[i]=max(v1[i-1],sum+dis[st[i]]+Mx);
		Mx=max(Mx,dis[st[i]]-sum);
	}
	LL tmp=b[top];Mx=sum=b[top]=0;
	for(int i=top;i>=1;i--){
		sum+=b[i];
		u2[i]=max(u2[i+1],sum+dis[st[i]]);
		v2[i]=max(v2[i+1],sum+dis[st[i]]+Mx);
		Mx=max(Mx,dis[st[i]]-sum);
	}
	LL Mn=v1[top];
	for(int i=1;i<top;i++)
		Mn=min(Mn,max(max(v1[i],v2[i+1]),tmp+u1[i]+u2[i+1]));
	ans=max(ans,Mn);
	printf("%.1lf",ans/2.0);	
	return 0;
}