[solution] LuoGu1073:Noip2009 optimal trade

The method comes from this big guy
LuoGu Title gate
[Abstract]
There is a very ingenious way to solve this problem: layered graph + SPFA
It can be seen from the question meaning that the output answer is only related to the buying and selling price, and the buying and selling are limited to one time
It's very difficult for us to maintain the status of buying and selling if it's general broad search, and it's also difficult to update the answer

This method is very convenient
Let's build a three-tier diagram

  1. First floor: initial road, can walk around without weight
  2. Layer 2: you can walk up and down the same floor as the first floor, but it comes from the first floor. A road is built from the first floor to the second floor, indicating purchase. The weight is - price
  3. Layer 3: you can walk up and down the same layer as the first layer, but it comes from the second layer. A road is built from the second layer to the third layer, which means selling. The weight is the price

And the end point is n in the third layer. The final result can be compared with 0
This method has a small code size and is very beautiful

Code:

uses math;
var
    q,dis,dist,next,u,head,w:array[0..1000000] of longint;
    vis:array[0..1000000] of boolean;
    n,m,x,y,z,i,h,tail,e,ans,num:longint;

procedure add(x,y,z:longint);

begin
    inc(num);
    u[num]:=y;
    dist[num]:=z;
    next[num]:=head[x];
    head[x]:=num;
end;

begin
    readln(n,m);
    for i:=1 to n do read(w[i]);
    for i:=1 to m do
    begin
        readln(x,y,z);
        add(x,y,0);
        add(x+n,y+n,0);
        add(x+n+n,y+n+n,0);
        add(x,y+n,-w[y]);
        add(x+n,y+n+n,w[y]);
        if z=2 then
        begin
            add(y,x,0);
            add(y+n,x+n,0);
            add(y+n+n,x+n+n,0);
            add(y,x+n,-w[x]);
            add(y+n,x+n+n,w[x]);
        end;
    end;
    q[1]:=1;
    tail:=1;
    for i:=2 to 3*n do dis[i]:=-maxlongint;
    while h<tail do
    begin
        inc(h);
        x:=q[h];
        vis[x]:=false;
        i:=head[x];
        while i>0 do
        begin
            e:=u[i];
            if (dis[e]<dis[x]+dist[i]) then
            begin
                dis[e]:=dis[x]+dist[i];
                if not vis[e] then
                begin
                    inc(tail);
                    q[tail]:=e;
                    vis[e]:=true;
                end;
                if e=3*n then ans:=max(ans,dis[e]);
            end;
            i:=next[i];
        end;
    end;
    writeln(ans);
end.

Posted on Mon, 06 Jan 2020 20:05:25 -0800 by philhale