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