50分求助
  • 板块P2656 采蘑菇
  • 楼主lizichang
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/10/27 17:10
  • 上次更新2023/10/27 05:36:16
查看原帖
50分求助
373819
lizichang楼主2022/10/27 17:10
#include<bits/stdc++.h>
#include<cstdio>
#include<stack>
#include<queue>
using namespace std;
const int N=8e4+5,M=2e5+5;
struct node
{
	int u,v,w,c,next;
}e[M];
struct final
{
	int v,w,next;
}edge[M];
stack<int> st;
int cnt,n,m,s,ans,tot,ts;
int low[N],dfn[N],bel[N],all[N],head[N],val[N],h[N],dis[N],sum[N];
bool vis[N];
void addedge(int x,int y,int z,int w)
{
	e[++cnt].u=x;
	e[cnt].v=y;
	e[cnt].w=z;
	e[cnt].c=w;
	e[cnt].next=head[x];
	head[x]=cnt;
}
void tarjan(int x)
{
	int to;
	dfn[x]=low[x]=++ts;
	st.push(x);
	vis[x]=1;
	for(int i=head[x];i;i=e[i].next)
	{
		to=e[i].v;
		if(!dfn[to])
		{
			tarjan(to);
			low[x]=min(low[x],low[to]);
		}
		else if(vis[to])	low[x]=min(low[x],low[to]);
	}
	if(low[x]==dfn[x])
	{
		tot++;
		while(!st.empty())
		{
			to=st.top();
			st.pop();
			bel[to]=tot;
			all[tot]++;
			vis[to]=0;
			if(to==x)	break;
		}
	}
}
void spfa(int x)
{
	int u,v,w;
	queue<int> q;
	memset(dis,-1,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[x]=val[x];
	q.push(x);
	vis[x]=1;
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		for(int i=h[u];i;i=edge[i].next)
		{
			v=edge[i].v,w=edge[i].w;
			//cout<<v<<' ';
			if(dis[v]<dis[u]+val[v]+w)
			{
				dis[v]=dis[u]+val[v]+w;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return ;
}
int main()
{
	int x,y,z,to,t,from;
	double w;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y>>z>>w;
		w*=100;
		addedge(x,y,z,w);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])	tarjan(i);
	cin>>s;
	cnt=0;
	for(int i=1;i<=m;i++)
	{
		from=e[i].u;
		to=e[i].v;
		if(bel[from]==bel[to])
		{
			t=e[i].w;
			while(t)
			{
				val[bel[from]]+=t;
				t=t*e[i].c/100;
			}
		}
		else
		{
			edge[++cnt].v=bel[to];
			edge[cnt].w=e[i].w;
			edge[cnt].next=h[bel[from]];
			h[bel[from]]=cnt;
		}
	}
	spfa(bel[s]);
	for(int i=1;i<=tot;i++)
		ans=max(ans,dis[i]);
	cout<<ans;
	return 0;
}
2022/10/27 17:10
加载中...