比赛 |
不平凡的世界 |
评测结果 |
WWWWWWTTTT |
题目名称 |
不平凡的引线 |
最终得分 |
0 |
用户昵称 |
FETS 1/3 |
运行时间 |
4.188 s |
代码语言 |
C++ |
内存使用 |
6.42 MiB |
提交时间 |
2015-11-05 11:51:48 |
显示代码纯文本
#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],double((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);
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",ans);
}