抢掠计划
比较水的缩点模板题，Tarjan缩点，重新建图，记录联通块的钱数、是否有酒吧
DAG上记忆化搜索即可
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define N 500010
inline int read(){
int x=; char c=getchar();
while(c<''||c>'') c=getchar();
while(''<=c&&c<='') { x=(x<<)+(x<<)+c-''; c=getchar(); }
return x;
}
int n,m,s,p,val[N],Val[N];
int head[N],to[N],next[N],sume;
bool ins[N],bar[N],Bar[N];
int dfn[N],low[N],stack[N],top,cnt,num;
int belong[N],Head[N],To[N],Next[N],Sume;
int f[N];
inline void add(int x,int y){
to[++sume]=y;
next[sume]=head[x];
head[x]=sume;
}
inline void Add(int x,int y){
To[++Sume]=y;
Next[Sume]=Head[x];
Head[x]=Sume;
}
inline void dfs(int t){ //Tarjan缩点
dfn[t]=low[t]=++cnt;
ins[t]=; stack[++top]=t;
for(int i=head[t];i;i=next[i]){
int v=to[i];
if(!dfn[v]){
dfs(v);
low[t]=min(low[t],low[v]);
}
else if(ins[v])
low[t]=min(low[t],dfn[v]);
}
if(low[t]==dfn[t]){
num++;
while(stack[top]!=t){
int k=stack[top];
belong[k]=num;
ins[k]=;
if(bar[k]) Bar[num]=;
Val[num]+=val[k];
top--;
}
belong[t]=num;
ins[t]=;
if(bar[t]) Bar[num]=;
Val[num]+=val[t];
top--;
}
}
bool dfs2(int u){ //记忆化搜索
if(f[u]) return f[u];
int maxx=; bool flag=Bar[u];
for(int i=Head[u];i;i=Next[i])
if(dfs2(To[i])){
flag=;
maxx=max(maxx,f[To[i]]);
}
if(flag) f[u]=maxx+Val[u];
else f[u]=;
return flag;
}
int main()
{
n=read(); m=read();
int x,y;
for(int i=;i<=m;i++){
x=read(); y=read();
add(x,y);
}
for(int i=;i<=n;i++)
val[i]=read();
s=read(); p=read();
for(int i=;i<=p;i++){
x=read();
bar[x]=;
}
dfs(s);
for(int u=;u<=n;u++) //重新建图
for(int j=head[u];j;j=next[j]){
int v=to[j];
if(belong[u]!=belong[v])
Add(belong[u],belong[v]);
}
dfs2(belong[s]);
printf("%d",f[belong[s]]);
return ;
}