【算法分析】
很简单，属于送分题类型。。。
缩点然后topsort+dp就可以了~
但是比较纠结的是会爆栈。。。。比赛不知道会不会的？听说Linux的栈比较大吧。。。
【CODE】
#include
const int INF=1000000000;
struct gtp{int x,y,next;}g[N];
int n,e,tot,S,head,tail,ans,stack;
int ls[N],fa[N],color[N],dep[N],list[N],du[N],w[N],F[N],v[N],edge[N],p[N];
bool ed[N];
inline void addedge(int x,int y){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e;
}
void input(){
int m,x,y;
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
addedge(x,y);
}
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
int num;
scanf("%d%d",&S,&num);
for (int i=1;i<=num;i++){
scanf("%d",&x);
ed[x]=true;
}
}
int gf(int k){
if (fa[k]==k) return k;
fa[k]=gf(fa[k]);
return fa[k];
}
void dfs(int k){
/*
for (int t=ls[k];t;t=g[t].next)
if (!dep[g[t].y]){
dep[g[t].y]=dep[k]+1;
dfs(g[t].y);
if (dep[gf(g[t].y)]
if (!color[gf(g[t].y)] && dep[gf(g[t].y)]
color[k]=1;
*/
stack=1; p[1]=k; edge[1]=ls[k];
while (stack){
int &t=edge[stack];
if (!t){
color[p[stack]]=1;
stack–;
continue;
}
if (!dep[g[t].y]){
dep[g[t].y]=dep[g[t].x]+1;
stack++;
p[stack]=g[t].y;
edge[stack]=ls[g[t].y];
}else
if (!color[gf(g[t].y)] && dep[gf(g[t].y)]
edge[stack]=g[edge[stack]].next;
}else edge[stack]=g[edge[stack]].next;
}
}
void tarjan(){
for (int i=1;i<=n;i++){
fa[i]=i;
color[i]=0;
dep[i]=0;
}
for (int i=1;i<=n;i++)
if (!dep[i]){
dep[i]=1;
dfs(i);
}
for (int i=1;i<=n;i++){
gf(i);
if (fa[i]!=i){
w[fa[i]]+=w[i];
if (ed[i]) ed[fa[i]]=true;
}
}
}
void changegraph(){
int te=e;
e=0; memset(ls,0,sizeof(ls));
for (int i=1;i<=te;i++)
if (fa[g[i].x]!=fa[g[i].y])
addedge(fa[g[i].x],fa[g[i].y]);
}
void topsort(){
memset(du,0,sizeof(du));
head=0; tail=0;
for (int i=1;i<=e;i++) du[g[i].y]++;
for (int i=1;i<=n;i++)
if (fa[i]==i && !du[i]) list[++tail]=i;
while (head
for (int t=ls[list[head]];t;t=g[t].next){
du[g[t].y]–;
if (!du[g[t].y]) list[++tail]=g[t].y;
}
}
}
void dp(){
memset(v,0,sizeof(v));
for (int i=1;i<=n;i++) F[i]=-INF;
ans=0;
head=1;
while (list[head]!=fa[S]) head++;
F[fa[S]]=0;
for (int k=head;k<=tail;k++){
int &i=list[k];
if (F[i]==-INF) continue;
F[i]+=w[i];
for (int t=ls[i];t;t=g[t].next)
if (v[g[t].y]!=i){
v[g[t].y]=i;
if (F[i]>F[g[t].y]) F[g[t].y]=F[i];
}
if (ed[i] && F[i]>ans) ans=F[i];
}
printf("%dn",ans);
}
int main(){
freopen("atm.in","r",stdin);
freopen("atm.out","w",stdout);
input();
tarjan();
changegraph();
topsort();
dp();
}