最优贸易 Editional

保存走到节点时的最小买入值，保存走到节点时的最大利润。为了利润最大，那么肯定就要以的价格买入最优，然后对于x节点，我们有卖与不卖(因为已经卖过了)的两种选择，不卖就直接从前驱节点继承，卖可以获得的利润就是，那么在这两个之间取最大。然后也不会受困于环，因为如若对于某节点，和都没有被更新，那么再继续搜索必定不会获得更优的答案（证明见下）。

相关证明:

为了方便表达，将停止处设为，最优买入点为。

(1)此时已经遍历过整个环，对于环上的任意一点都已经取到了最小值且都相等，且这个最小值为。因此，必定存在无法更新。

(2)表示在一直经过到的路径上卖出的利润，同(1)可以推知，遍历完成之后也是确定的，那么必定存在无法更新。(1)(2)表明这个搜索必定会停下。

正确性证明： 仅表示在此节点可以选取的最优买入点，以在后来的节点进行卖出时状态转移，但与并不相互干扰，当后继节点的卖出值无法达到足够大时，不会被更新，其总保存最优答案且得到了所有的方案。

Code:

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f,maxn=100010,maxm=500010;
struct data{
    int v,nxt;
}edge[maxm<<1];
int n,m,p,head[maxn],c[maxn],f[maxn],mi[maxn];
void insert(int u,int v)
{
    edge[++p].v=v;
    edge[p].nxt=head[u];
    head[u]=p;
}
void input()
{
    int u,v,k;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>c[i];
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v;
        insert(u,v);
        cin>>k;
        if(k==2) insert(v,u);
    }
}
void dfs(int x,int minx,int pre)
{
    bool b=true;
    if(minx>c[x]) minx=c[x];
    if(mi[x]>minx) mi[x]=minx,b=false;
    int maxx=(c[x]-minx>f[pre]?c[x]-minx:f[pre]);
    if(f[x]<maxx) f[x]=maxx,b=false;
    if(b) return ;
    for(int i=head[x];i;i=edge[i].nxt) dfs(edge[i].v,minx,x);
}
int main()
{
    input();
    memset(mi,0x3f,sizeof(mi));
    dfs(1,INF,0);
    printf("%d\n",f[n]);
    return 0;
}