7分求调
查看原帖
7分求调
1072191
huangmingyisunny楼主2024/2/26 22:16
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=500005;
struct Node{
    int u,v;
}a[500005];
struct node{
	int y,w;
};
int dfn[M],low[M],sum,cnt,scc[M],res[M],mo[M],id[M],n,dis[M],w[M],ans[M];
bool vis[M];
vector<int> nbr[M],nuber[M];
vector</*node*/int> new_nbr[M];
stack<int> s;
void tarjan(int cur){
    s.push(cur);
    vis[cur]=1;
    dfn[cur]=low[cur]=++cnt;
    for(int i=0;i<nbr[cur].size();i++){
        int nxt=nbr[cur][i];
        if(!dfn[nxt]){
            tarjan(nxt);
            low[cur]=min(low[cur],low[nxt]);
        }else if(vis[nxt]){
        	low[cur]=min(low[cur],dfn[nxt]);
        }
    }
    if(dfn[cur]==low[cur]){ 	
    	cnt++;
        while(s.top()!=cur){
			int tmp=s.top();
			s.pop();
            vis[tmp]=0;
            scc[tmp]=cnt;
            ans[cnt]+=w[tmp];
            nuber[cnt].push_back(tmp);
//            cout<<tmp<<" "<<cnt<<" "<<w[tmp]<<"\n";
        }
        
        s.pop();
        vis[cur]=0;
        scc[cur]=cnt;
        ans[cnt]+=w[cur];
        nuber[cnt].push_back(cur);
//		cout<<cur<<" "<<cnt<<" "<<w[cur]<<" "<<ans[cnt]<<"\n";
    }
    return ;
}
void spfa(int s){
	queue<int> q;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		dis[i]=-2147483647;
	}
	dis[s]=ans[scc[s]];
	q.push(s);
	vis[s]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int k=0;k<nuber[scc[x]].size();k++){
//			cout<<k<<" 1 "<<nuber[scc[x]].size()<<" ";
			int j=nuber[scc[x]][k];
			dis[j]=max(ans[scc[x]],dis[j]);
//			cout<<j<<endl;
			for(int i=0;i<new_nbr[j].size();i++){
//				cout<<i<<" 2 "<<new_nbr[j].size()<<" "; 
				int y=new_nbr[j][i];
//				cout<<j<<" "<<y<<endl;
//				cout<<x<<" "<<y<<" "<<dis[y]<<" "<<dis[j]<<" "<<ans[scc[y]]<<" ";
				if(dis[j]+ans[scc[y]]>dis[y]){
					dis[y]=dis[j]+ans[scc[y]];
//					cout<<dis[y]<<"\n";
					if(vis[y]==0){
						vis[y]=1;
						q.push(y);
					}
				}
			}
		}
	}
	return;
}
signed main(){
	int m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		a[i].u=x;
	    a[i].v=y;
		nbr[x].push_back(y);
	}
	for(int i=1;i<=n;i++){
		cin>>w[i];
	} 
	cnt=0;
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=m;i++){
        int x=scc[a[i].u];
        int y=scc[a[i].v];
		if(x!=y){
			new_nbr[a[i].u].push_back(/*(node){*/a[i].v/*,w[a[i].v]}*/);
		}
	}
	int s,p;
	cin>>s;
	spfa(s);
	cin>>p;
	int maxi=0xcfcfcfcfcfcfcfcf;
	for(int i=1;i<=p;i++){
		cin>>m;
		int x=maxi;
		maxi=max(maxi,dis[m]);
	}
	cout<<maxi;
	return 0;
}
2024/2/26 22:16
加载中...