水题不过 87分求调
查看原帖
水题不过 87分求调
722313
Whiking楼主2023/8/25 16:20
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<iterator>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define Genshin_Impact_starts ios::sync_with_stdio(false)
//#define int long long
#define F first
#define S second
#define eps 1e-6
#define RE register
#define IN inline
#define For(i,s,t) for(register int i=s;i<=t;i++)
#define rFor(i,s,t) for(register int i=s;i>=t;i--)
#define eFor(i,u) for(register int i=head[u];i;i=nxt[i])
#define ls(i) tr[i].ch[0]
#define rs(i) tr[i].ch[1]
#define son(i,op) tr[i].ch[op]
#define siz(i) tr[i].siz
#define fa(i) tr[i].fa
#define val(i) tr[i].val
using namespace std;
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
void swap(int &a,int &b){a=a^b,b=a^b,a=a^b;}
const int N=1e6+100,inf=1e9+10;
int n,m,s,p,ans;
int ve[N],is[N],dp[N],in[N];
vector<int>G[N],G2[N];
map<pair<int,int>,int>key;
struct edge{
	int u,v;
}E[N];
struct Tarjan{
	int scc[N],dfn[N],low[N],vis[N],siz[N],bar[N],tot,co;
	stack<int>s;
	void init(){
		tot=0;
	}
	void tarjan(int u){
		dfn[u]=low[u]=++tot;
		vis[u]=1;
		s.push(u);
		for(auto v:G[u])
			if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
			else if(vis[v])low[u]=min(low[u],dfn[v]);
		if(low[u]!=dfn[u])return;
		++co;
		int v;
		do{
			v=s.top();
			s.pop();
			scc[v]=co;
			vis[v]=0;
			siz[co]+=ve[v];
			if(!bar[co])bar[co]=is[v];
		}while(v!=u);
	}
}T;
signed main(){
    Genshin_Impact_starts;
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    For(i,1,m)
    	cin>>E[i].u>>E[i].v,
    	G[E[i].u].push_back(E[i].v);
	For(i,1,n)cin>>ve[i];
	cin>>s>>p;
	For(i,1,p){
		int x;cin>>x;
		is[x]=1;
	}
	For(i,1,n)if(!T.dfn[i])T.tarjan(i);
	For(i,1,m){
		int u=T.scc[E[i].u],v=T.scc[E[i].v];
		if(u!=v){
			G2[u].push_back(v),in[v]++;
		}
	}
	n=T.co,s=T.scc[s];
	queue<int>q;
	q.push(s);
	dp[s]=T.siz[s];
	while(q.size()){
		int u=q.front();
		q.pop();
		for(auto v:G2[u]){
			dp[v]=max(dp[v],dp[u]+T.siz[v]);
			if(T.bar[v])ans=max(ans,dp[v]);
			if(!--in[v])q.push(v);
		}
	}
	cout<<ans;
}
2023/8/25 16:20
加载中...