比赛 |
不平凡的世界 |
评测结果 |
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);
}