比赛 |
20121107 |
评测结果 |
APPPP |
题目名称 |
小树 |
最终得分 |
95 |
用户昵称 |
as |
运行时间 |
0.007 s |
代码语言 |
C |
内存使用 |
1.99 MiB |
提交时间 |
2012-11-07 11:08:53 |
显示代码纯文本
/*
COGS
P1256
*/
#include<stdio.h>
#include<string.h>
#include<assert.h>
#define MAXN 1010
int T,n;
int f[MAXN];
int d[MAXN],s[MAXN];
int head[MAXN],next[MAXN],u[MAXN],v[MAXN],w[MAXN];
int queue[MAXN],front,rear,isq[MAXN];
FILE *fin,*fout;
int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}
void spfa(int start)
{
memset(s,0,sizeof(s));
memset(isq,0,sizeof(isq));
s[start]=0;
front=rear=0;
queue[rear++]=start;
while(front!=rear)
{
int x=queue[front++];
front%=n+1;
isq[x]=0;
int e;
for(e=head[x];e!=-1;e=next[e])
if(s[v[e]]<s[x]+w[e])
{
s[v[e]]=s[x]+w[e];
if(!isq[v[e]])
{
queue[rear++]=v[e];
rear%=n+1;
}
}
}
}
void spfa2(int start)
{
memset(d,0,sizeof(d));
memset(isq,0,sizeof(isq));
front=rear=0;
queue[rear++]=start;
while(front!=rear)
{
int x=queue[front++];
isq[x]=0;
front%=n+1;
int e;
for(e=head[x];e!=-1;e=next[e])
{
d[v[e]]=d[x]+1;
if(!isq[v[e]])
{
isq[v[e]]=1;
queue[rear++]=v[e];
rear%=n+1;
}
}
}
}
int main()
{
int i;
fin=fopen("treec.in","r");fout=fopen("treec.out","w");
assert(fin&&fout);
fscanf(fin,"%d",&T);
while(T)
{
memset(head,-1,sizeof(head));
fscanf(fin,"%d",&n);
if(n==1)
{
fprintf(fout,"0.00\n");
T--;
continue;
}
for(i=0;i<=n;i++)
f[i]=i;
for(i=0;i<n-1;i++)
{
fscanf(fin,"%d%d%d",&u[i],&v[i],&w[i]);
next[i]=head[u[i]],head[u[i]]=i;
int x=find(u[i]),y=find(v[i]);
f[y]=x;
}
int root=find(1);
spfa(root);
spfa2(root);
double ans=0.0;
for(i=0;i<n;i++)
if(i!=root)
{
double d1=(double)s[i],d2=(double)d[i];
double tmp=d1/d2;
ans=ans>tmp?ans:tmp;
}
fprintf(fout,"%.2lf\n",ans);
T--;
}
fclose(fin);fclose(fout);
return 0;
}