题解 P1807 【最长路_NOI导刊2010提高（07）】

why_always_china · 2015-08-20 16:22:00 · 题解

这道题可以用拓扑排序做，但是要注意的一个地方就是要对数据预处理一下。根据题目，找出从1到n的最长路，那么我们要预处理掉1以外其他入度为0的点，以及除去它们之后衍生出来的入度为0的点......否则，将会对后面的拓扑排序造成影响，具体怎么影响的就是有的点可能除不干净入度。可以用BFS实现。状态转移方程f[j]:=max(f[j],f[i]+v[i,j])（f[j]:1-j的最长路径)。

附Pascal代码（里面有一些很奇怪的没用的地方，属于我看不懂题目而加的保险，请自行判断去留）：

program foodweb;
const maxn=1501;
      maxm=50001;
var h,d,f,q:array[1..maxn] of longint;
    v,next,w:array[1..maxm] of longint;
    i,j,k,p,n,m,l,hd,tl,s,nt:longint;
function mx(a,b:longint):longint;
begin
    if a>b then exit(a) else exit(b);
end;
procedure swap;
begin
    if i=j then exit;
    i:=i xor j;
    j:=i xor j;
    i:=i xor j;
end;
begin
    read(n,m);
    fillchar(f,sizeof(f),0);
    fillchar(d,sizeof(d),0);
    fillchar(h,sizeof(h),0);
    p:=0;

    for k:=1 to m do
    begin
        read(i,j,l);
        inc(p);
        if i>=j then swap;
        v[p]:=j;
        w[p]:=l;
        inc(d[j]);
        next[p]:=h[i];
        h[i]:=p;
    end;
    f[n]:=-1;
    hd:=0;tl:=0;
    for i:=2 to n do
    begin
        if d[i]=0 then
        begin
            inc(tl);
            q[tl]:=i;
        end;
    end;
    while hd<tl do
    begin
        inc(hd);
        s:=q[hd];
        nt:=h[s];
        while nt>0 do
        begin
            dec(d[v[nt]]);
            if d[v[nt]]=0 then
            begin
                inc(tl);
                q[tl]:=v[nt];
            end;
            nt:=next[nt];
        end;
    end;
    hd:=0;tl:=0;

    inc(tl);
    q[tl]:=1;
    while hd<tl do
    begin
        inc(hd);
        s:=q[hd];
        nt:=h[s];
        while nt>0 do
        begin
            dec(d[v[nt]]);
            if d[v[nt]]=0 then
            begin
                inc(tl);
                q[tl]:=v[nt];
            end;
            f[v[nt]]:=mx(f[v[nt]],f[s]+w[nt]);
            nt:=next[nt];
        end;
    end;
    writeln(f[n]);
end.