首先用Tarjan缩下点
那么就是一个有向无环图上的dp了。。我写的记忆化搜索
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
// <1179.cpp> - 07/28/16 20:25:25 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <stack> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=1000010; const int INF=1e9; int bt,b[MAXN],next[MAXN],to[MAXN]; inline void add(int y,int x){next[++bt]=b[x];b[x]=bt;to[bt]=y;} int tot,dfn[MAXN],low[MAXN],f[MAXN]; lol a[MAXN]; bool in[MAXN],ex[MAXN]; stack <int> st; void dfs(int x){ dfn[x]=low[x]=++tot; st.push(x);in[x]=1; for(int i=b[x];i;i=next[i]) if(!dfn[to[i]]){ dfs(to[i]); low[x]=min(low[x],low[to[i]]); }else if(in[to[i]])low[x]=min(low[x],dfn[to[i]]); if(dfn[x]==low[x]){ for(int i=b[x];i;i=next[i])to[i]=f[to[i]]; int sec; while(1){ sec=st.top();st.pop(); in[sec]=0; f[sec]=x; if(sec==x)break; a[x]+=a[sec]; for(int i=b[sec];i;i=next[i]){ if(f[to[i]]==x)continue; add(f[to[i]],x); } } } } lol ans[MAXN]; lol dfs2(int x){ in[x]=1; lol get=0; for(int i=b[x];i;i=next[i]){ if(!in[to[i]])ans[to[i]]=dfs2(to[i]); get=max(get,ans[to[i]]); } if(get)return get+a[x]; return ex[x]*a[x]; } int main(){ int n=gi(),m=gi(); for(int i=1;i<=m;i++)add(gi(),gi()); for(int i=1;i<=n;i++)a[i]=gi(); for(int i=n;i;i--)if(!dfn[i])dfs(i); int s=f[gi()],p=gi(); for(int i=1;i<=p;i++)ex[f[gi()]]=1; printf("%lld",dfs2(s)); return 0; } |
说点什么