POJ3249Test for Job（拓扑排序+DP）

program test;
type
  point=^node;
  node=record
       data:longint;
       next:point;
    end;
var
  a:array[0..100000]of point;
  w,u,v,dis,f:array[0..100000]of int64;
  n,i,m,t,x,y,num:longint;
  ans:int64;
  p:point;
function max(x,y:int64):int64;
begin
  if x>y then max:=x else max:=y;
end;
begin
  while  not eof do
  begin
  readln(n,m);
  for i:=1 to n do
    readln(w[i]);
  for i:=1 to n do
    a[i]:=nil;
  t:=0;  ans:=-maxlongint; num:=0;
  fillchar(u,sizeof(u),0);  fillchar(v,sizeof(v),0);
  for i:=1 to m do
   begin
     readln(x,y);
     new(p); p^.data:=y; p^.next:=a[x]; a[x]:=p;
     u[y]:=u[y]+1; v[x]:=v[x]+1;
   end;
  for i:=1 to n do dis[i]:=-maxlongint;
  for i:=1 to n do if u[i]=0 then begin inc(t); f[t]:=i; dis[i]:=w[i]; end;
  repeat
    x:=f[t]; dec(t); inc(num);
    new(p); p:=a[x];
    while p<>nil do
     begin
       y:=p^.data; dis[y]:=max(dis[y],dis[x]+w[y]);
       dec(u[y]);
       if u[y]=0 then
        begin
          inc(t); f[t]:=y;
        end;
       p:=p^.next;
     end;
  until num=n;
  for i:=1 to n do
   if v[i]=0 then ans:=max(ans,dis[i]);
  writeln(ans);
  end;
end.