tarjan+dp 87pts WA#3#11求助
查看原帖
tarjan+dp 87pts WA#3#11求助
766339
Crazyouth楼主2023/11/11 11:49
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
vector<int> G[N],G2[N];
int dp[N],dfn[N],low[N],scc[N],a[N],isp[N],isp2[N],scccnt=0,dfncnt=0,ins[N],newa[N],n,m,s,p,vis[N];
stack<int> st;
void tarjan(int u)
{
	dfn[u]=low[u]=++dfncnt;
	ins[u]=1;
	st.push(u);
	for(auto v:G[u])
	{
		if(!dfn[v])
		{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(ins[v]) low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		++scccnt;
		while(st.top()!=u)
		{
			scc[st.top()]=scccnt;
			newa[scccnt]+=a[st.top()];
			ins[st.top()]=0;
			isp2[scccnt]|=isp[st.top()];
			st.pop();
		}
		scc[st.top()]=scccnt;
		newa[scccnt]+=a[st.top()];
		ins[st.top()]=0;
		isp2[scccnt]|=isp[st.top()];
		st.pop();
	}
}
void dfs(int u)
{
	vis[u]=1;
	dp[u]+=newa[u];
	for(auto v:G2[u])
	{
		if(vis[v]) continue;
		dp[v]+=dp[u];
		dfs(v);
	}
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
	}
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>s>>p;
	for(int i=1;i<=p;i++)
	{
		int t;
		cin>>t;
		isp[t]=1;
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
	for(int i=1;i<=n;i++)
	{
		for(auto j:G[i])
		{
			if(scc[i]!=scc[j]) G2[scc[i]].push_back(scc[j]);
		}
	}
	dfs(scc[s]);
	int ans=0;
	for(int i=1;i<=scccnt;i++) if(isp2[i]) ans=max(ans,dp[i]);
	cout<<ans;
	return 0;
}
2023/11/11 11:49
加载中...