最优贸易 Editional

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

相关证明:

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

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

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

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

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;
}