萌新求助样例没过输出62
查看原帖
萌新求助样例没过输出62
642481
Esawkm楼主2023/7/8 11:52

RT

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n,m,ans=-INT_MAX,dfn[1000005],dis[1000005],viss[1000005],s,u[1000005],jb[1000005],v[1000005],p,cnt,w[1000005],hd[1000005],val[1000005],nxt[1000005],to[1000005],low[1000005],d[1000005],vis[1000005],in[1000005],top,tot,sta[1000005],co,scc[1000005],sz[1000005];
queue<int>q;
void add(int u,int v){
	to[++cnt]=v;
	nxt[cnt]=hd[u];
	hd[u]=cnt;
}
void addd(int u,int v,int w){
	to[++cnt]=v;
	nxt[cnt]=hd[u];
	val[cnt]=w;
	hd[u]=cnt;
}
void tarjan(int x){
	low[x]=dfn[x]=++tot;
	sta[++top]=x;
	in[x]=1;
	for(int i(hd[x]);i;i=nxt[i]){
		int u=to[i];
		if(!dfn[u]){
			tarjan(u);
			low[x]=min(low[x],low[u]);
		}
		else if(in[u])
		low[x]=min(low[x],dfn[u]);
	}
	if(dfn[x]==low[x]){
		++co;
		while(sta[top]!=x){
			int k=sta[top];
			scc[k]=co;
			sz[co]+=w[top];
			in[k]=0;
			top--;
		}
		int k=sta[top];
		scc[k]=co;
		sz[co]+=w[top];
		in[k]=0;
		top--;
	}
}
void spfa(int x){
	memset(dis,128,sizeof(dis));
	q.push(scc[x]);
	viss[scc[x]]=1,dis[scc[x]]=sz[scc[x]];
	while(!q.empty()){
		int l=q.front();
		q.pop();
		viss[l]=0;
		for(int i(hd[l]);i;i=nxt[i]){
			if(dis[to[i]]<dis[l]+val[i]){
				dis[to[i]]=dis[l]+val[i];
				if(!viss[to[i]])
				q.push(to[i]),viss[to[i]]=1;
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i(1),x,y;i<=m;i++)
	cin>>x>>y,u[i]=x,v[i]=y,add(x,y);
	for(int i(1);i<=n;i++)
	cin>>w[i];
	cin>>s>>p;
	for(int i(1);i<=p;i++)
	cin>>jb[i];
	for(int i(1);i<=n;i++)
	if(!dfn[i])
	tarjan(i);
	cnt=0;
	memset(hd,0,sizeof(hd));
	memset(to,0,sizeof(to));
	memset(nxt,0,sizeof(nxt));
	memset(vis,0,sizeof(vis));
	for(int i(1);i<=m;i++)
	if(scc[u[i]]!=scc[v[i]])
	addd(scc[u[i]],scc[v[i]],sz[scc[v[i]]]);
	spfa(s);
	for(int i(1);i<=p;i++)
	ans=max(ans,dis[scc[jb[i]]]);
	cout<<ans;
	return 0;
}
2023/7/8 11:52
加载中...