比赛 |
不平凡的世界 |
评测结果 |
AAAAAAAAAA |
题目名称 |
不平凡的引线 |
最终得分 |
100 |
用户昵称 |
Mayuri |
运行时间 |
0.205 s |
代码语言 |
C++ |
内存使用 |
6.04 MiB |
提交时间 |
2017-09-05 19:35:36 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))
const int maxN=100001;
const int maxM=(maxN+1)*2;
const int inf=2147483647;
class Edge
{
public:
int u,v,w;
double finishtime;
};
class Queue_Data
{
public:
int number;
double t;
};
bool operator < (Queue_Data A,Queue_Data B)
{
return A.t>B.t;
}
int n,m;
int cnt=-1;
int Head[maxN];
int Next[maxM];
Edge E[maxM];
bool inqueue[maxM];
bool is_finish[maxM];
int Degree[maxN];
priority_queue<Queue_Data> Q;
int read();
void Add_Edge(int u,int v,int w);
int main()
{
freopen("firelead.in","r",stdin);
freopen("firelead.out","w",stdout);
mem(Head,-1);
mem(Degree,0);
mem(inqueue,0);
mem(is_finish,0);
m=read();n=m+1;
for (int i=1;i<=m;i++)
{
int u=read(),v=read(),w=read();
Add_Edge(u,v,w);
Add_Edge(v,u,w);
Degree[u]++;
Degree[v]++;
}
for (int i=1;i<=n;i++)
if (Degree[i]==1)
{
if (inqueue[Head[i]^1]==0)
{
Q.push((Queue_Data){Head[i],1.0*E[Head[i]].w});
inqueue[Head[i]]=1;
E[Head[i]].finishtime=1.0*E[Head[i]].w;
}
else if (inqueue[Head[i]]==0)
{
Q.push((Queue_Data){Head[i],1.0*E[Head[i]].w/2});
inqueue[Head[i]]=1;
E[Head[i]].finishtime=1.0*E[Head[i]].w/2;
}
}
/*
for (int i=0;i<=cnt;i++)
cout<<'['<<i<<"] "<<E[i].u<<"->"<<E[i].v<<" "<<E[i].w<<endl;
cout<<endl;
//*/
double Ans=0;
do
{
Queue_Data now=Q.top();
Q.pop();
int edgenum=now.number;
//int u=E[edgenum].u;
int v=E[edgenum].v;
/*
for (int i=0;i<=cnt;i++)
cout<<inqueue[i]<<" ";
cout<<endl;
for (int i=0;i<=cnt;i++)
cout<<is_finish[i]<<" ";
cout<<endl<<endl;
//*/
if ((is_finish[edgenum]==1)||(is_finish[edgenum^1]==1))
continue;
is_finish[edgenum]=is_finish[edgenum^1]=1;
//cout<<u<<"->"<<v<<"finish!"<<endl;
//cout<<"finish time:"<<now.t<<endl;
Ans=max(Ans,now.t);
for (int i=Head[v];i!=-1;i=Next[i])
{
if ((is_finish[i]==1)||(inqueue[i]==1)||(is_finish[i^1]==1))
continue;
if (inqueue[i^1]==1)
{
Q.push((Queue_Data){i,1.0*(E[i^1].finishtime-now.t)/2+now.t});
//cout<<"Push edge1:"<<E[i].u<<"->"<<E[i].v<<" "<<1.0*(E[i^1].finishtime-now.t)/2+now.t<<endl;
//cout<<" "<<E[i^1].finishtime<<' '<<now.t<<endl;
inqueue[i]=1;
}
else
{
Q.push((Queue_Data){i,1.0*E[i].w+now.t});
E[i].finishtime=1.0*E[i].w+now.t;
//cout<<"Push edge2:"<<E[i].u<<"->"<<E[i].v<<" "<<1.0*E[i].w+now.t<<endl;
inqueue[i]=1;
}
}
//cout<<endl;
}
while (!Q.empty());
printf("%.1f",Ans);
fclose(stdin);
fclose(stdout);
return 0;
}
int read()
{
int x=0;
int k=1;
char ch=getchar();
while (((ch>'9')||(ch<'0'))&&(ch!='-'))
ch=getchar();
if (ch=='-')
{
k=-1;
ch=getchar();
}
while ((ch>='0')&&(ch<='9'))
{
x=x*10+ch-48;
ch=getchar();
}
return x*k;
}
void Add_Edge(int u,int v,int w)
{
cnt++;
Next[cnt]=Head[u];
Head[u]=cnt;
E[cnt].u=u;
E[cnt].v=v;
E[cnt].w=w;
return;
}