只在第三个点 T 飞了,1.03s
做法是缩点后在 DAG 上跑 dp,但不知道为什么非常之慢。
#include<bits/stdc++.h>
#define N 500200
#define il inline
using namespace std;
int n,m,s,p,ans,id;
int a[N],w[N],f[N];
int dfn[N],low[N],scc[N],ind;
bool ins[N],qwq[N];
stack<int>st;
vector<int>g[N],g1[N];
bool con[8000][8000];
il void tarjan(int u)
{
dfn[u]=low[u]=++ind;ins[u]=1;st.push(u);
for(int 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(low[u]==dfn[u])
{
id++;
while(1)
{
int v=st.top();st.pop();
ins[v]=0;scc[v]=id;
if(u==v)break;
}
}
}
il void dfs(int u,int sum)
{
sum+=w[u];
if(sum<=f[u])return;
f[u]=sum;
if(qwq[u])ans=max(ans,sum);
for(int v:g1[u])dfs(v,sum);
}
namespace in
{
char buf[1<<25],*p1=buf,*p2=buf;
inline int getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
template <typename T>inline void read(T& t){
t=0;int f=0;char ch=getc();while (!isdigit(ch)){if(ch=='-')f = 1;ch=getc();}
while(isdigit(ch)){t=t*10+ch-48;ch = getc();}if(f)t=-t;
}
template <typename T,typename... Args> inline void read(T& t, Args&... args){read(t);read(args...);}
}
int main()
{
// freopen("P3627_3.in","r",stdin);
// freopen("1.out","w",stdout);
in::read(n,m);
for(int i=1,u,v;i<=m;++i)
{
in::read(u,v);
g[u].push_back(v);
}
for(int i=1;i<=n;++i)in::read(a[i]);
in::read(s,p);
tarjan(s);
for(int i=1;i<=n;++i)w[scc[i]]+=a[i];
for(int i=1;i<=n;++i)
{
for(int j:g[i])
{
if(scc[i]==scc[j]||con[scc[i]][scc[j]])continue;
g1[scc[i]].push_back(scc[j]);
con[scc[i]][scc[j]]=1;
}
}
for(int i=1,x;i<=p;++i)
{
in::read(x);
qwq[scc[x]]=1;
}
dfs(scc[s],0);
printf("%d\n",ans);
}