如何解决精度问题
  • 板块P2656 采蘑菇
  • 楼主31415926P
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/9/12 20:55
  • 上次更新2023/11/4 06:55:43
查看原帖
如何解决精度问题
345003
31415926P楼主2021/9/12 20:55
#include<bits/stdc++.h>
using namespace std;
#define M 500100
int from[M],first[M],next[M],to[M],in[M],dfn[M],low[M],sd[M],tot,tim,top,Tot;
int n,m,stac[M],vis[M],p[M],s,W[M];
int From[M],First[M],Next[M],TTo[M],dis[M],w[M],ww[M];
inline void Add(int x,int y,int z)
{
	Tot++;
	Next[Tot]=First[x];
	First[x]=Tot;
	TTo[Tot]=y;
	W[Tot]=z;
}
inline void add(int x,int y,int z,int q)
{
	tot++;
	next[tot]=first[x];
	first[x]=tot;
	to[tot]=y;
	from[tot]=x;
	w[tot]=z;
	ww[tot]=q;
}
void tarjan(int x)
{
	low[x]=dfn[x]=++tim;
	stac[++top]=x,vis[x]=1;
	for(int i=first[x];i;i=next[i])
	{
		int lmh=to[i];
		if(dfn[lmh]==0)
		{
			tarjan(lmh);
			low[x]=min(low[x],low[lmh]);
		}
		else if(vis[lmh]==1)
		{
			low[x]=min(low[x],low[lmh]);
		}
	}
	if(dfn[x]==low[x])
	{
		int y;
		while(y=stac[top--])
		{
			sd[y]=x;
			vis[y]=0;
			if(x==y)break;
		}
	}
}
queue<int> d;
void spfa()
{
	dis[sd[s]]=p[sd[s]];
	while(!d.empty())
	{
		int x=d.front();
		d.pop();
		for(int i=First[x];i;i=Next[i])
		{
			int lmh=TTo[i];
			if(dis[lmh]<dis[x]+W[i]+p[lmh])
			{
				dis[lmh]=dis[x]+W[i]+p[lmh];
					d.push(lmh);
				
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		ans=max(ans,dis[i]);
	}
	cout<<ans;
}
int main()
{
//	freopen("2.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v,z;
		string y;
		int lj;	
		cin>>u>>v>>z>>y;
		if(y.length()==1)lj=0;
		else lj=(y[2]-'0')*100;
		add(u,v,z,lj);
	}
	for(int i=1;i<=n;i++)
	{
		if(dfn[i]==0)
			tarjan(i);
	}
	for(int i=1;i<=m;i++)
	{
		int x=from[i],y=to[i];
		if(sd[x]!=sd[y])Add(sd[x],sd[y],w[i]);
		else
		{
			int hhhh=w[i];
			while(hhhh)
			{
				p[sd[x]]+=hhhh;
				hhhh=hhhh*ww[i]/1000;
			}
		}
	}
	cin>>s;
	d.push(sd[s]);
	spfa();
	return 0;
	
}
2021/9/12 20:55
加载中...