蹲个大佬来解答555
查看原帖
蹲个大佬来解答555
433518
名字好难取144楼主2023/7/24 14:40

90 pts,RE #7,蹲个大佬来解答 代码如下(去掉头文件等不重要内容):

const ll N=5e5+10;

struct edge{
	ll from,next,to,w;
}e[N],ex[N];

ll head[N],exhead[N],dfn[N],low[N],stark[N],ind[N];

ll point[N],dis[N],dist[N],color[N];

bool vis[N];

ll cnt,sum,n,m,ans,top,tot,cnt1;

void add(ll u,ll v)
{
	e[++cnt].next=head[u];
	e[cnt].from=u;
	e[cnt].to=v;
	//e[cnt].w=w;
	head[u]=cnt;
}

void add_(ll u,ll v)
{
	ex[++cnt1].next=exhead[u];
	ex[cnt1].from=u;
	ex[cnt1].to=v;
	//e[cnt].w=w;
	exhead[u]=cnt1;
}

void tarjan(ll u)
{
	vis[u]=1;
	dfn[u]=low[u]=++sum;
	stark[++top]=u;
	for(ll i=head[u];i;i=e[i].next)
	{
		ll v=e[i].to;
		if(!vis[v]) {tarjan(v);low[u]=min(low[u],low[v]);} 
		if(vis[v])
		{
			low[u]=min(low[u],low[v]);
		}
	}
	//cout<<1<<"\n";
	if(dfn[u]==low[u])
	{
		tot++; ll y=stark[top];
		while(1)
		{
			y=stark[top--];
			color[y]=tot;
			vis[y]=0;
			dis[tot]+=point[y];
			if(y==u) break;
		}
	}
}


void spfa()
{
	//cout<<1<<endl;
	ll sum=0;
	memset(dist,-0x3f,sizeof(dist));
	memset(vis,false,sizeof(vis)); 
	queue<ll> q;
	for(ll i=1;i<=tot;++i) {
		if(ind[i]==0) {
			q.push(i);
			vis[i]=1;
			dist[i]=dis[i];
		}
	}
	//q.push(x);
	//vis[x]=true;dist[x]=0;
	while(!q.empty())
	{
		ll x;
		x=q.front();q.pop();
		vis[x]=false;
		sum=max(sum,dist[x]+dis[x]); 
		for(ll i=exhead[x];i;i=ex[i].next)
		{
			ll y=ex[i].to;
			if(dist[y]<dist[x]+dis[y])
			dist[y]=dist[x]+dis[y];// 更新 
			if(vis[y]) continue;
			q.push(y);
		}
	}
	return ;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("q.in","r",stdin);
	freopen("q.out","w",stdout);
#endif		
	n=read();m=read();
	for(ll i=1;i<=n;++i) point[i]=read();
	for(ll i=1,u,v;i<=m;++i)
	{
		u=read(); v=read();
		add(u,v);
	}
	//cout<<1<<endl;
	for(ll i=1;i<=n;++i)
	{
		if(dfn[i]==0) tarjan(i);
	}
	//cout<<1<<endl;
	for(ll i=1;i<=n;++i)
	{
		for(ll j=head[i];j;j=e[j].next)
		{
			if(color[i]!=color[e[j].to]) {
				add_(color[i],color[e[j].to]);
				ind[color[e[j].to]]++;
			}
		}
	}
	//cout<<1<<endl;
	spfa();ans=-1;
	for(ll i=1;i<=tot;++i)
	{
		ans=max(ans,dist[i]);
	}
	printf("%d",ans);
	return 0;
}
2023/7/24 14:40
加载中...