提交记录

就是 Tarjan 缩点之后在 DAG 上做 DP，和缩点模版差不多。

玄关。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+5;
struct graph {
    struct enode {
        int nxt,to;
    } edge[N];
    int tot,head[N];
    void add(int u,int v) {
        edge[++tot].to=v;
        edge[tot].nxt=head[u];
        head[u]=tot;
    }
} G,T;
int n,m,a[N];
int low[N],dfn[N],cnt,st[N],top,bel[N],siz[N],idx,sum[N];
bool ins[N];
void tarjan(int u) {
    low[u]=dfn[u]=++cnt;
    st[++top]=u;
    ins[u]=1;
    for(int i=G.head[u];i;i=G.edge[i].nxt) {
        int v=G.edge[i].to;
        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]) {
        idx++;
        int v;
        do {
            v=st[top--];
            ins[v]=0;
            bel[v]=idx;
            siz[idx]++;
            sum[idx]+=a[v];
        } while(v!=u);
    }
}
int ind[N],dp[N];
bool ed[N];
void toposort(int u) {
    bool flag=ed[u];
    for(int i=T.head[u];i;i=T.edge[i].nxt) {
        flag=1;
        int v=T.edge[i].to;
        toposort(v);
        dp[u]=max(dp[u],dp[v]);
    }
    if(flag) dp[u]+=sum[u];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++) {
        cin>>u>>v;
        G.add(u,v);
    }
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++) {
        for(int j=G.head[i];j;j=G.edge[j].nxt) {
            int v=G.edge[j].to;
            if(bel[i]!=bel[v]) {
                T.add(bel[i],bel[v]);
                ind[bel[v]]++;
            }
        }
    }
    int st,k;
    cin>>st>>k;
    T.add(0,bel[st]);
    ind[bel[st]]++;
    for(int i=1,x;i<=k;i++) {
        cin>>x;
        ed[bel[x]]=1;
    }
    toposort(0);
    cout<<dp[0]<<'\n';
    return 0;
}