这种tarjan+dp的水题我竟然还WA了两次,要小心!
type link=^node;
node=record
po:longint;
next:link;
end; var rd,be,st,v,a,dp,dfn,low:array[..] of longint;
f,b,bar:array[..] of boolean;
edge,way:array[..] of link;
h,t,i,n,m,beg,bs,s,x,y:longint;
p:link; procedure add(y:longint;var q:link);
var p:link;
begin
new(p);
p^.po:=y;
p^.next:=q;
q:=p;
end; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure tarjan(x:longint);
var y:longint;
p:link; begin
inc(h);
inc(t);
st[t]:=x;
dfn[x]:=h;
low[x]:=h;
f[x]:=true;
p:=way[x];
while p<>nil do
begin
y:=p^.po;
if dfn[y]= then
begin
tarjan(y);
low[x]:=min(low[x],low[y]);
end
else if f[y] then low[x]:=min(low[x],low[y]);
p:=p^.next;
end;
if dfn[x]=low[x] then
begin
inc(s);
while st[t+]<>x do
begin
y:=st[t];
f[y]:=false;
be[y]:=s;
v[s]:=v[s]+a[y];
dec(t);
end;
end;
end; begin
readln(n,m);
for i:= to m do
begin
readln(x,y);
add(y,way[x]);
end;
for i:= to n do
readln(a[i]); readln(beg,bs);
for i:= to bs do
begin
read(x);
b[x]:=true;
end; for i:= to n do
if dfn[i]= then
begin
h:=;
t:=;
tarjan(i);
end; for i:= to n do
begin
p:=way[i];
while p<>nil do
begin
y:=p^.po;
if be[i]<>be[y] then
begin
add(be[i],edge[be[y]]);
inc(rd[be[i]]);
end;
p:=p^.next;
end;
if b[i] then bar[be[i]]:=true;
end; t:=;
for i:= to s do
if rd[i]= then
begin
inc(t);
st[t]:=i;
end; h:=;
while h<=t do
begin
x:=st[h];
dp[x]:=max(dp[x],v[x]);
p:=edge[x];
while p<>nil do
begin
y:=p^.po;
if bar[x] then
begin
dp[y]:=max(dp[y],dp[x]+v[y]);
bar[y]:=true;
end;
dec(rd[y]);
if rd[y]= then
begin
inc(t);
st[t]:=y;
end;
p:=p^.next;
end;
inc(h);
end;
writeln(dp[be[beg]]);
end.