题解 P1073 【最优贸易】

· · 题解

看到大家的题解都没有缩点DP的，我就乱写了一个。由于本人水平太渣，直接深搜，有点爆栈，只有90分，不过据说linux栈会略大一点，或许就可以水过了。所以本题解并不适合复制，仅供参考。

思路比较好想：强联通分量之间是拓扑的，再加上50%的数据没有环，这就暗示我们，可以缩点DP。我在这里采用了tarjan算法来求出强联通分量，分别记录最小和最大价格。然后缩点时，我不知道有什么好方法，就直接建了一个新图，然后DP,方程大体类似SPFA。

program trade;
const maxn=100001;
      maxm=500001;
      maxq=200000;
var h,h2,dfn,low,stack,naive,big,small,rd,new,money:array[1..maxn] of longint;
    queue:array[1..200003] of longint;
    visit,f:array[1..maxn] of boolean;
    v,v2,next,nt:array[1..maxm] of longint;
    n,p,hd,tl,i,s,t,deep,d,m,qs,z,num:longint;
function min(a,b:longint):longint;
begin
    if a>b then exit(b) else exit(a);
end;
function max(a,b:longint):longint;
begin
    if a>b then exit(a) else exit(b);
end;
procedure print(x:longint);
begin
    while stack[deep]<>x do
    begin
        new[stack[deep]]:=x;
        big[x]:=max(big[x],naive[stack[deep]]);
        small[x]:=min(small[x],naive[stack[deep]]);
        f[stack[deep]]:=false;
        dec(deep);
    end;
    new[stack[deep]]:=x;
    big[x]:=max(big[x],naive[stack[deep]]);
    small[x]:=min(small[x],naive[stack[deep]]);
    f[stack[deep]]:=false;
    dec(deep);
end;
procedure dfs(x:longint);
var i,qs:longint;
begin
    inc(d);
    dfn[x]:=d;
    low[x]:=d;
    inc(deep);
    stack[deep]:=x;
    f[x]:=true;
    qs:=h[x];
    while qs>0 do
    begin
        if not visit[v[qs]] then
        begin
            visit[v[qs]]:=true;
            dfs(v[qs]);
            low[x]:=min(low[x],low[v[qs]]);
        end
        else
            if f[v[qs]] then low[x]:=min(low[x],dfn[v[qs]]);
        qs:=next[qs];
    end;
    if dfn[x]=low[x] then print(x);
end;

begin

    fillchar(visit,sizeof(visit),false);
    fillchar(f,sizeof(f),false);
    fillchar(h,sizeof(h),0);
    fillchar(h2,sizeof(h2),0);
    fillchar(new,sizeof(new),0);
    fillchar(big,sizeof(big),0);
    fillchar(small,sizeof(small),1);
    fillchar(rd,sizeof(rd),0);
    fillchar(money,sizeof(money),0);
    read(n,m);
    p:=0;
    for i:=1 to n do read(naive[i]);
    for i:=1 to m do
    begin
        read(s,t,z);
        inc(p);
        v[p]:=t;
        next[p]:=h[s];
        h[s]:=p;
        if z=2 then
        begin
            inc(p);
            v[p]:=s;
            next[p]:=h[t];
            h[t]:=p;
        end;
    end;
    for i:=1 to n do if not visit[i] then
    begin
        visit[i]:=true;
        dfs(i);
    end;
    p:=0;
    for i:=1 to n do
    begin
        qs:=h[i];
        while qs>0 do
        begin
            t:=v[qs];
            if new[t]<>new[i] then
            begin
            inc(p);
            inc(rd[new[t]]);
            v2[p]:=new[t];
            nt[p]:=h2[new[i]];
            h2[new[i]]:=p;
            end;
            qs:=next[qs];
        end;
    end;
    hd:=0;
    tl:=0;
    num:=0;
    for i:=1 to n do if (rd[i]=0)and(i=new[i]) then
    begin
        tl:=tl mod maxq +1;
        queue[tl]:=i;
        inc(num);
    end;
    while num>0  do
    begin
        hd:=hd mod maxq+1;
        qs:=h2[queue[hd]];
        dec(num);
        while qs>0 do
        begin
            t:=v2[qs];
            dec(rd[t]);
            small[t]:=min(small[t],small[queue[hd]]);
            money[t]:=max(money[queue[hd]],big[t]-small[t]);
            if rd[t]=0 then
            begin
                tl:=tl mod maxq +1;
                queue[tl]:=t;
                inc(num);
            end;
            qs:=nt[qs];
        end;
    end;
    if (money[new[n]])>0 then
    writeln(money[new[n]]) else writeln(0);
end.