记录编号	205560	评测结果	WWWWWWTTTT
题目名称	不平凡的引线	最终得分	0
用户昵称	FETS 1/3	是否通过	未通过
代码语言	C++	运行时间	4.143 s
提交时间	2015-11-05 16:06:25	内存使用	5.14 MiB

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int maxn=100050;
struct edge
{
	int x;
	int y;
	int v;
	int ne;
};
edge e[maxn*2];
int qdb[maxn];
int t=0;
inline void insert(int xx,int yy,int vv)
{
	e[++t].x=xx;
	e[t].y=yy;
	e[t].v=vv;
	e[t].ne=qdb[xx];
	qdb[xx]=t;
}
struct node
{
	int sd;
	int bh;
};
node jd[maxn];
int m;
int ds[maxn];
int q[maxn];
int vis[maxn];
double js[maxn];//第i个结点已经被彻底烧干净！
int head=1;
int tail=0;
void bfs(int st)
{
	head=1,tail=0;
	memset(vis,0,sizeof(vis));
	q[++tail]=st;
	vis[st]=1;
	jd[st].sd=0;
	jd[st].bh=st;
	for(;head<=tail;head++)
	{
		for(int i=qdb[q[head]];i;i=e[i].ne)
		{
			if(!vis[e[i].y])
			{
				q[++tail]=e[i].y;
				jd[e[i].y].sd=jd[e[i].x].sd+1;
				jd[e[i].y].bh=e[i].y;
				vis[e[i].y]=1;
			}
		}
	}
}
bool mycmp(node x,node y)
{
	return x.sd<y.sd;
}
void dfs(int x)
{
	for(int i=qdb[x];i;i=e[i].ne)
	{
		if(!vis[e[i].y])
		{
			if(js[e[i].y]<e[i].v+js[e[i].x])
				js[e[i].y]=max(js[e[i].y],(e[i].v-js[e[i].x])/2+js[e[i].y]);
			else 
				js[e[i].y]=js[e[i].x]+e[i].v;
			vis[e[i].y]=1;
			dfs(e[i].y);
		}
	}
}
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	scanf("%d",&m);
	for(int i=1;i<=m-1;i++)
	{
		int u,v,len;
		scanf("%d %d %d",&u,&v,&len);
		len=len*2;
		insert(u,v,len);
		insert(v,u,len);
		ds[u]++;
		ds[v]++;
	}
	int id=0;
	for(int i=1;i<=m;i++)
	{
		if(ds[i]!=1)
		{
			id=i;
			break;
		}
	}
	bfs(id);
	sort(jd+1,jd+m+1,mycmp);
	memset(js,0,sizeof(js));
	for(int i=1;i<=m;i++)
	{
		memset(vis,0,sizeof(vis));
		if(ds[jd[i].bh]==1)
		{
			js[jd[i].bh]=0;
			dfs(i);
		}
	}
	double ans=-1.0;
	for(int i=1;i<=m;i++)
	{
		ans=max(ans,js[i]);
	}
	printf("%.1lf",double(ans/2));
}