比赛 不平凡的世界 评测结果 TTTTTTEEEE
题目名称 不平凡的引线 最终得分 0
用户昵称 coo 运行时间 6.412 s
代码语言 C++ 内存使用 0.37 MiB
提交时间 2015-11-05 11:58:10
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<map>
using namespace std;
int m,n=0,k,u,v,s;
double t=0;
int dist[10005]={0};
struct date{
	int fa,dis;
}d[1005];
bool bb[1005]={0};
vector<int>p[1005];
queue<int>q;
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>u>>v>>s;
		p[u].push_back(v);
		p[v].push_back(u);
		d[v].fa=u;
		d[u].fa=v;
		dist[u]++;
		dist[v]++;
	}
	while(n!=m)
	{
		for(int i=1;i<=m;i++)
	    if(dist[i]==1){
		dist[i]=0;
		dist[d[i].fa]--;
		bb[d[i].fa]=1;
	    }
	    for(int i=1;i<=m;i++)
	    if(bb[i]==1)
	    {
	    	int tt=1;
	    	for(int j=0;j<p[i].size();j++)
	    	{
	    		if(bb[p[i][j]]==1)tt++;
	    	    t+=1.0/tt;
	    	    dist[i]--;
	    	    dist[j]--;
			}
			dist[i]--;
		 } 
	    for(int i=1;i<=m;i++)
	    if(dist[i]==0)n++;
	}
	t+=1;
	printf("%.1lf",t);
	return 0;
}