做法:

先scc缩点然后拓扑排序dp

非递归,2次AC

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=500005;
struct edge
{
    int y;
    edge * next;
};
edge * li[maxn];
edge * new_edge()
{
    static edge a[1000005];
    static int top=0;
    return &a[top++];
}
void insert_edge(int x,int y)
{
    edge * t=new_edge();
    t->y=y;
    t->next=li[x];
    li[x]=t;
}
int money[maxn];
int new_money[maxn];
int bar[maxn];
int new_bar[maxn];
int belong_to[maxn];
int dfn[maxn],low[maxn];
int x[maxn],y[maxn];
bool inque[maxn];
int tot=0;
void scc(int x)
{
    static int que[maxn];
    static int father[maxn];
    father[x]=-1;
    int now=0;
    int rail=0;
    for (;;)
    {
        if (x==-1) return;
        if (dfn[x]==-1)
        {
            dfn[x]=now++;
            low[x]=dfn[x];
            que[rail++]=x;
            inque[x]=true;
        }
        for (;li[x]!=0;li[x]=li[x]->next)
        {
            if (dfn[li[x]->y]==-1)
            {
                father[li[x]->y]=x;
                x=li[x]->y;
                break;
            }
            if (inque[li[x]->y])
            {
                low[x]=min(low[x],low[li[x]->y]);
            }
        }
        if (dfn[x]==-1) continue;
        if (low[x]==dfn[x])
        {
            for (;;)
            {
                rail--;
                belong_to[que[rail]]=tot;
                inque[que[rail]]=false;
                if (que[rail]==x) break;
            }
            tot++;
        }
        x=father[x];
    }
}
int max_ans;
int in[maxn];
int dp[maxn];
void topo_sort()
{
    int i;
    for (i=0;i<tot;i++)
    {
        edge * t;
        for (t=li[i];t!=0;t=t->next)
        {
            in[t->y]++;
        }
    }
    static int que[maxn];
    int front=0,rail=0;
    for (i=0;i<tot;i++)
    {
        if (in[i]==0) que[rail++]=i;
        dp[i]=new_money[i];
    }
    for (;front<rail;front++)
    {
        int now=que[front];
        if (new_bar[now]) max_ans=max(max_ans,dp[now]);
        edge * t;
        for (t=li[now];t!=0;t=t->next)
        {
            in[t->y]--;
            dp[t->y]=max(dp[t->y],dp[now]+new_money[t->y]);
            if (in[t->y]==0)
            {
                que[rail++]=t->y;
            }
        }
    }
}
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    for (i=0;i<m;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        x[i]--;
        y[i]--;
        insert_edge(x[i],y[i]);
    }
    for (i=0;i<n;i++)
    {
        scanf("%d",&money[i]);
    }
    int q;
    int s;
    scanf("%d",&s);
    scanf("%d",&q);
    for (i=0;i<q;i++)
    {
        int x;
        scanf("%d",&x);
        x--;
        bar[x]=true;
    }
    memset(belong_to,-1,sizeof(belong_to));
    memset(dfn,-1,sizeof(dfn));
    s--;
    scc(s);
    for (i=0;i<n;i++)
    {
        if (belong_to[i]==-1) continue;
        new_bar[belong_to[i]]|=bar[i];
        new_money[belong_to[i]]+=money[i];
    }
    memset(li,0,sizeof(li));
    for (i=0;i<m;i++)
    {
        if (belong_to[x[i]]==-1) continue;
        if (belong_to[y[i]]==-1) continue;
        if (belong_to[x[i]]==belong_to[y[i]]) continue;
        insert_edge(belong_to[x[i]],belong_to[y[i]]);
    }
    topo_sort();
    printf("%d\n",max_ans);
    return 0;
}