比赛 |
20121107 |
评测结果 |
EEEEE |
题目名称 |
小树 |
最终得分 |
0 |
用户昵称 |
skyfisherman |
运行时间 |
0.358 s |
代码语言 |
C++ |
内存使用 |
3.16 MiB |
提交时间 |
2012-11-07 10:27:48 |
显示代码纯文本
#include <iostream>
#include <cstdio>
using namespace std;
struct Line{
int x,l;
Line *next;
Line(int a,int b,Line *c):
x(a), l(b), next(c) {}
}* G[1000];
double ans;
int queue[1001],sd[1001],sw[1001],F[1001],h,t;
void BFS(){
queue[0]=0; F[0]=-1;
int h=0, t=1, x;
while(h<t){
x=queue[h++];
for(Line *p=G[x];p;p=p->next)
if(p->x!=F[x])
queue[t++]=p->x,
sd[p->x]=sd[x]+1,
sw[p->x]=sw[x]+p->l,
F[p->x]=x;
}
}
int n,m;
void solve(){
int a,b,c; double ans=0;
scanf("%d",&n);m=n-1;
while(m--){
scanf("%d%d%d",&a,&b,&c);
G[a]=new Line(b,c,G[a]);
G[b]=new Line(a,c,G[b]);
}
BFS();
for(int i=1;i<n;i++)ans=max(ans,(double)sw[i]/sd[i]);
printf("%.2lf",ans);
}
int main(){
freopen("treec.in","r",stdin);
freopen("treec.out","w",stdin);
int T;
scanf("%d",&T);
while(T--)solve();
}