题解 P1073 【最优贸易】
HY喵
2018-01-26 21:18:35
**看到楼上有$dalao$用$tarjan$缩点+拓扑排序+$dp$的，也有用$spfa$双向广搜的，都用了将近$100$行代码。**
**但是我只用了暴力+动规。**
大佬轻喷。
**接下来讲具体解法。**
**第一**、输入。存邻接表
**第二**、我们需要做深搜。可以用递归来做，同时做动规：
函数如下（贴了注释）.
```cpp
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;
**第四**、变量说明与初始化：
```cpp
vector<int> g[MAXN];
int n,m,f[MAXN],mi[MAXN],c[MAXN];
```
g是邻接表，n,m如题目所示；
c是商品价值，mi是最小商品价值，f是动规状态变量。
初始化：mi都为无穷大。
**第五**、主程序
```cpp
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行的代码在这里：**
```cpp
#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;
}
```