题解 P1073 【最优贸易】

看到楼上有dalao用tarjan缩点+拓扑排序+dp的，也有用spfa双向广搜的，都用了将近100行代码。

但是我只用了暴力+动规。

大佬轻喷。

接下来讲具体解法。

第一、输入。存邻接表

第二、我们需要做深搜。可以用递归来做，同时做动规：

函数如下（贴了注释）.

void dfs(int x,int minx,int pre) {                           //x表示当前访问的节点编号，minx表示目前为止的最小的商品价格，pre表示上一个节点的编号
    int flag=1;                                          //用于判断是否已被访问过，需要终止
    minx=min(c[x],minx);                                 //判断本次的商品价格是否是最小值
    if (mi[x]>minx) mi[x]=minx,flag=0;                   //判断mi数组（记录了每次的最小值）并更新，在更新的同时把flag设为0（不用退出了）
    做动态规划；                                         //别着急flag还会继续更新的
    if (flag) return;                                    //退出，千万不能露，不然程序就会放飞自我，堆栈溢出->完美MLE只有10分。
    for (int i=0;i<g[x].size();i++) dfs(g[x][i],minx,x); //继续进行递归调用，访问目前节点能访问到的节点。
}

第三、动态规划：

状态f[x]的含义如下：走到第x个节点为止最多赚的旅费。

方程如下：f[x]=\max(f[prev],c[x]-minx)

最终输出的是：走到第N个节点为止最大旅费，即f[n]。

再次展示一下我的华丽的代码（就是void dfs的“做动态规划”）。讲得太清楚了连注释都不需要了:)

int maxx=max(f[pre],c[x]-minx);
if (f[x]<maxx) f[x]=maxx,flag=0;

第四、变量说明与初始化：

vector<int> g[MAXN];
int n,m,f[MAXN],mi[MAXN],c[MAXN];

g是邻接表，n,m如题目所示；

c是商品价值，mi是最小商品价值，f是动规状态变量。

初始化：mi都为无穷大。

第五、主程序

int main() {
    scanf("%d%d",&n,&m);                               //输入
    for (int i=0;i<MAXN;i++) mi[i]=INF;                //初始化
    for (int i=1;i<=n;i++) scanf("%d",&c[i]);          //输入
    for (int i=1;i<=m;i++) {                           //输入
        int t1,t2,t3;                                  //输入
        scanf("%d%d%d",&t1,&t2,&t3);                   //输入
        g[t1].push_back(t2);                           //邻接表
        if (t3==2) g[t2].push_back(t1);                //邻接表
    }                                                  //大括号
    dfs(1,INF,0);                                      //关键只有一行
    printf("%d\n",f[n]);                               //输入
    return 0;                                          //再见
}                                                      //大括号

最后，整个只有32行的代码在这里：

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define MAXN 100005
using namespace std;

vector<int> g[MAXN];
int n,m,f[MAXN],mi[MAXN],c[MAXN];

void dfs(int x,int minx,int pre) {
    int flag=1; 
    minx=min(c[x],minx);
    if (mi[x]>minx) mi[x]=minx,flag=0;
    int maxx=max(f[pre],c[x]-minx);
    if (f[x]<maxx) f[x]=maxx,flag=0;
    if (flag) return;
    for (int i=0;i<g[x].size();i++) dfs(g[x][i],minx,x);
}

int main() {
    scanf("%d%d",&n,&m);
    for (int i=0;i<MAXN;i++) mi[i]=INF;
    for (int i=1;i<=n;i++) scanf("%d",&c[i]);
    for (int i=1;i<=m;i++) {
        int t1,t2,t3;
        scanf("%d%d%d",&t1,&t2,&t3);
        g[t1].push_back(t2);
        if (t3==2) g[t2].push_back(t1);
    }
    dfs(1,INF,0);
    printf("%d\n",f[n]);
    return 0;
}