比赛 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();
}