【题解】P1073 [NOIP2009 提高组] 最优贸易

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

有\(n\)个城市\(m\)条道路，每条道路连接这\(n\)个城市中的某两个城市。任意城市之间最多只有一条道路相连。

这\(m\)条道路中有一部分为单向通行的道路，一部分为双向通行的道路。双向道路在统计时记为一条。

同一商品在不同城市价格\(c\)不同，但同一商品在城市中的买入和卖出价格是相同的。商人想要通过赚差价赚出旅费，且他只进行一次贸易，求最多能赚多少。

$$

1n ,~1m

$$

分析

用动态规划即可解决。定义\(f_i\)为走到结点\(i\)为止赚的最多的钱。 $ f_i=(f_{pre},c_i-minx) $ 同时进行深搜即可。

实现

\((381ms,~4.58mb)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<bits/stdc++.h>

const int N = 100005;
using namespace std;
int n, m, dp[N], c[N], minn[N];
struct node {
    int next, to;
} e[N << 2];
int head[N], tmp;

void add(int x, int y) {
    e[++tmp].to = y;
    e[tmp].next = head[x];
    head[x] = tmp;
}

void dfs(int x, int minx, int pre) {
    bool book = true;
    minx = min(c[x], minx);
    if (minn[x] > minx) {
        minn[x] = minx;
        book = false;
    }
    int maxx = max(dp[pre], c[x] - minx);
    if (dp[x] < maxx) {
        dp[x] = maxx;
        book = false;
    }
    if (book) return;
    for (int i = head[x]; i; i = e[i].next) {
        dfs(e[i].to, minx, x);
    }
}

int main() {
    cin >> n >> m;
    memset(minn, 0x3f, sizeof minn);
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= m; i++) {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        add(t1, t2);
        if (t3 == 2) add(t2, t1);
    }
    dfs(1, 0x3f3f3f3f, 0);
    cout << dp[n];
    return 0;
}