比赛 不平凡的世界 评测结果 TTTTTTEEEE
题目名称 不平凡的引线 最终得分 0
用户昵称 momo123 运行时间 6.529 s
代码语言 C++ 内存使用 0.28 MiB
提交时间 2015-11-05 11:57:30
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
int d[2000],t,m,n,sum;
vector<int>p[2005];
queue <int>q;
double ans;
void addedge(int a,int b)
{
	p[a].push_back(b);
	p[b].push_back(a);
	d[a]++;
	d[b]++;
}
void work()
{
	while(t!=n)
	{
		for(int i=1;i<=q.size();i++)
		{
			int k=q.front();
			q.pop();
		    for(int j=0;j<p[k].size();j++)
	            d[p[k][j]]--;
	    }
	    for(int kk=1;kk<=n;kk++)
	    {
	            if(d[kk]==1) 
				{
				  q.push(kk);
				  d[kk]==-1;
				  t++;
				  sum++;
			    }
			    if(d[kk]==0) 
				{
				  t++;
				  sum=0;;
			    }
		}
	    if(q.size()==2&&t==n&&sum==0) ans+=0.5;
	      else ans++;
	}
}
int main()
{
	freopen("firelead.in","r",stdin);
	freopen("firelead.out","w",stdout);
	cin>>m;
	n=m+1;
	for(int i=1;i<=m;i++)
	{
		int u,v,len;
		cin>>u>>v>>len;
		addedge(u,v);
	}
	if(n==2)
	{
	  cout<<"0.5"<<endl;
	  return 0;
    }
	for(int i=1;i<=n;i++)
	   if(d[i]==1)
	   {
	      q.push(i);
	      d[i]=-1;
	      t++;
	      sum++;
	   }
    work();
    printf("%.1lf",ans);
}