Luogu P1073 最优贸易

YorkWu

May 21, 2019

1181 views

No comments

919 words

随笔题目

[题目链接](https://www.luogu.org/problemnew/show/P1073 "题目链接")

* * *

这道题没太明白。。。 题解好多种方法，我就看了看第一种方法。 动态规划+dfs $f\[x\]$表示到x节点所能拿到差价的最大值。 状态转移方程：$f\[x\]=max(f\[fa\],c\[x\]-minx)$ $c\[x\],minx$分别是x节点的售价和到x节点的路上的最小售价。 剩下的写注释吧。 代码：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,m,w[100009];
    struct Edge{
        int to,nxt;
    }e[1000009];
    int head[100009],tot;
    
    int f[100009],minn[100009];
    
    void add(int x,int y){
        e[++tot].to=y;
        e[tot].nxt=head[x];
        head[x]=tot;
    }
    
    void dfs(int x,int fa,int minx){
        int pd=1;//这个就是判断要不要继续找下去的一个变量。
        minx=min(minx,w[x]);//更新minx
        if(minx<minn[x]) minn[x]=minx,pd=0;//minn保存的是到x节点最小值，这里就是如果最小值小于上一次访问这个节点的最小值，就更新。
        int maxx=max(f[fa],w[x]-minx);//dp
        if(f[x]<maxx) f[x]=maxx,pd=0;//这里是如果这次最大值大于上次访问这个节点时候的最大值，就要把这个新的值传递下去，直到全部传递完。
        //其实就是这里不太明白。。。
        if(pd) return;
        for(int i=head[x];i;i=e[i].nxt){
            int y=e[i].to;
            dfs(y,x,minx);
        }
    }
    
    int main(){
        cin>>n>>m;
        memset(minn,0x3f,sizeof(minn));
        for(int i=1;i<=n;i++) cin>>w[i];
        for(int i=1;i<=m;i++){
            int x,y,op;
            cin>>x>>y>>op;
            if(op==1) add(x,y);
            else add(x,y),add(y,x);
        }
        dfs(1,0,0x3f3f3f3f);
        cout<<f[n];
        return 0;
    }
```

Last modification：March 14, 2020