比赛 |
20121107 |
评测结果 |
APPPP |
题目名称 |
小树 |
最终得分 |
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;
}