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