真不知道怎么写的,才7pts,求条
查看原帖
真不知道怎么写的,才7pts,求条
1135241
Lyx8058楼主2025/2/4 19:59
#include<bits/stdc++.h>
using namespace std;
const int N=500010;
int n,m,v[N],v_D[N],s,p,a,u,w,in[N],dfn[N],low[N],timi,cnt,stac[N],stac_size,b[N],f[N];
vector<int>e[N];
vector<int>e_D[N];
map<int,int>mp;
map<int,int>mp_D;
void Tarjan(int x){
	dfn[x]=low[x]=++timi;
	stac[++stac_size]=x;
	for(auto k:e[x]){
		if(!dfn[k]){
			Tarjan(k);
			low[x]=min(low[x],low[k]);
		}
		else if(!b[k]) low[x]=min(low[x],dfn[k]);
	}
	if(dfn[x]==low[x]){
		cnt++;
		while(stac[stac_size]!=x)
		{
			mp_D[cnt]=mp[stac[stac_size]];
			v_D[cnt]+=v[stac[stac_size]];
			b[stac[stac_size--]]=cnt;
		}
		mp_D[cnt]=mp[stac[stac_size]];
		v_D[cnt]+=v[stac[stac_size]];
		b[stac[stac_size--]]=cnt;
	}
}
void DAG(){
	for(int i=1;i<=n;i++){
		if(b[i]){
			for(auto j:e[i]){
				if(b[i]==b[j]) continue;
				in[b[j]]++;
				e_D[b[i]].push_back(b[j]);
			}
		}
	}
}
int tops(){
	queue<int>q;
	q.push(b[s]);
	f[b[s]]=v_D[b[s]];
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(auto k:e_D[x]){
			if(f[k]<f[x]+v_D[k]){
				f[k]=max(f[k],f[x]+v_D[k]);
				if(--in[k]==0) q.push(k);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=cnt;i++){
		if(mp_D[i]) ans=max(ans,f[i]);
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>w;
		e[u].push_back(w);
	}
	for(int i=1;i<=n;i++){
		cin>>v[i];
	}
	cin>>s>>p;
	for(int i=1;i<=p;i++){
		cin>>a;
		mp[a]=1;
	} 
	Tarjan(s);
	DAG();
	cout<<tops()<<"\n";
	return 0;
}
2025/2/4 19:59
加载中...