比赛 20121107 评测结果 A
题目名称 小树 最终得分 95
用户昵称 QhelDIV 运行时间 0.009 s
代码语言 C++ 内存使用 3.66 MiB
提交时间 2012-11-07 09:23:37
显示代码纯文本
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
using namespace std;
ifstream fin("treec.in");
ofstream fout("treec.out");
int T,N;
double Ans,S;
class Node
{
public:
	int name;
	double weight;
	Node *Prev;
}*last[100001];
void Add(int u,int v,int w)
{
Node *temp=new Node;
	temp->name=v;temp->weight=w;temp->Prev=last[u];
	last[u]=temp;
}
void DFS(int pos,double Wi,double Di)
{
Node *temp;
	S=max(S,Wi/Di);
	for(temp=last[pos];temp;temp=temp->Prev)
		DFS(temp->name,Wi+temp->weight,Di+1);
}
int main()
{
int i,j;
	for(i=0;i<=100000;i++)
		last[i]=NULL;
	fin>>T;
	for(i=1;i<=T;i++)
	{
		fin>>N;
		for(j=0;j<N;j++)
			while(last[j]!=NULL)
			{
			Node *temp=last[j]->Prev;
				free(last[j]);
				last[j]=temp;
			}
		//initialize
		for(j=1;j<N;j++)
		{
		int U,V,W;
			fin>>U>>V>>W;
			Add(U,V,W);
		}
		//read
	double Ti=0.0;
		Ans=0.0;
		for(Node *temp=last[0];temp;temp=temp->Prev)
		{
			S=0;
			DFS(temp->name,temp->weight,1.0);
			Ans=max(Ans,S);
			Ti=Ti+1;
		}
		
		fout<<setiosflags(ios::fixed)<<setprecision(2)<<Ans<<endl;
	}
	fin.close();
	fout.close();
	return 0;
}