「一本通 3.2 练习 5」最优贸易

GitHub跳转原题关系图返回列表

在有向图上通过正反向 SPFA/队列松弛预处理前缀最小买入价与后缀最大卖出价，枚举中间中转城市求解最大单笔贸易利润。

OJ: roj

题目 ID: 1501

难度:提高

标签:图论最短路SPFA

创建: 2026-09-30 14:51

更新: 2026-10-07 11:01

形式化题目

给定一个包含 $n$ 个顶点和 $m$ 条边的有向图（部分边为双向边），每个顶点 $u$ 有一个点权 $p_u$ （表示该城市水晶球价格）。要求找到一条从顶点 $1$ 出发、最终到达顶点 $n$ 的可行路径，并在路径上选择两个顶点 $u, v$ （ $u$ 在路径中出现的位置不晚于 $v$ ），使得差价 $p_v - p_u$ 最大。若无法获利或最大差价为负，则可以不进行贸易，收益为 $0$ 。图中节点和边均可重复经过。

graph LR
    S((1)) -->|路径前段| U((u: 买入))
    U -->|前缀最小价| I((i: 中转点))
    I -->|后缀最大价| V((v: 卖出))
    V -->|路径后段| T((n))

上图展示了最优贸易的路径拆分思想：任意一笔在 $u$ 买入、在 $v$ 卖出的合法交易，都可以通过中间经过的城市（例如交界点 $i$ ）拆分成“从 $1$ 到 $i$ 的最低进价”与“从 $i$ 到 $n$ 的最高售价”。

正解

思路

直接在任意有向图中寻找一条包含买卖两点的路径非常复杂，因为路径可以经过环且节点可重复访问。我们可以通过枚举中转节点将全局贸易问题分解为两个独立的极值可达性问题：

状态分解：假设阿龙在城市 $u$ 买入水晶球，在城市 $v$ 卖出水晶球，整条旅行路线为 $1 \leadsto u \leadsto v \leadsto n$ 。我们可以在 $u$ 和 $v$ 之间（甚至直接令 $i = v$ ）选取一个中转城市 $i$ 。这样，整个贸易的最大收益可以分解为两部分：
- 在从 $1$ 到 $i$ 的可行路径中，所能遇到的最低商品价格，记为 $D_{\min}[i]$ 。
- 在从 $i$ 到 $n$ 的可行路径中，所能遇到的最高商品价格，记为 $D_{\max}[i]$ 。如果在城市 $i$ 处决策，则通过城市 $i$ 的最大可能收益为 $D_{\max}[i] - D_{\min}[i]$ 。
正向图松弛求解 $D_{\min}$ ：
- 设 $D_{\min}[x]$ 为从城市 $1$ 到城市 $x$ 的所有路径中经过的城市的最低商品价格。
- 初始时 $D_{\min}[1] = p_1$ ，其余点设为 $+\infty$ 。
- 考虑有向边 $u \to v$ ：若当前已经能在走到 $u$ 时买到价格为 $D_{\min}[u]$ 的商品，则沿该边走到 $v$ 时，能在途中买到的最低价格为 $\min(D_{\min}[u], p_v)$ 。
- 若该值比已记录的 $D_{\min}[v]$ 更小，则更新 $D_{\min}[v]$ ，并将 $v$ 加入队列继续松弛。
反向图松弛求解 $D_{\max}$ ：
- 设 $D_{\max}[x]$ 为从城市 $x$ 出发能够到达城市 $n$ 的所有路径中经过的城市的最高商品价格。
- “从 $x$ 走向 $n$ ”等价于“在反向图上从 $n$ 走向 $x$ ”。
- 初始时 $D_{\max}[n] = p_n$ ，其余点设为 $-1$ 。
- 在反向图上，若当前沿反向边到达 $v$ 能卖出的最高价格 $\max(D_{\max}[u], p_v)$ 大于 $D_{\max}[v]$ ，则更新 $D_{\max}[v]$ 并将 $v$ 入队。
合并求最优答案：遍历所有城市 $i \in [1, n]$ 。若城市 $i$ 既可从 $1$ 到达（ $D_{\min}[i] \leqslant 100$ ），又能到达 $n$ （ $D_{\max}[i] \geqslant 0$ ），则其对答案的贡献为 $D_{\max}[i] - D_{\min}[i]$ 。最终答案即为所有中转城市的收益最大值（若均小于等于 $0$ 则输出 $0$ ）。

代码

Python 版：

python

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 14:55
# update_at: 2026-09-30 14:55

import sys
from collections import deque

INF = 10**9


def compute_min_prices(n: int, prices: list[int], graph: list[list[int]]) -> list[int]:
    """计算从 1 号城市到达各城市路径上的最小买入价格。"""
    min_p = [INF] * (n + 1)
    min_p[1] = prices[1]
    queue: deque[int] = deque([1])

    while queue:
        u = queue.popleft()
        p = min_p[u]
        for v in graph[u]:
            cand = min(p, prices[v])
            if cand < min_p[v]:
                min_p[v] = cand
                queue.append(v)
    return min_p


def compute_max_prices(n: int, prices: list[int], rev_graph: list[list[int]]) -> list[int]:
    """计算从各城市出发到达 n 号城市路径上的最大卖出价格。"""
    max_p = [-1] * (n + 1)
    max_p[n] = prices[n]
    queue: deque[int] = deque([n])

    while queue:
        u = queue.popleft()
        p = max_p[u]
        for v in rev_graph[u]:
            cand = max(p, prices[v])
            if cand > max_p[v]:
                max_p[v] = cand
                queue.append(v)
    return max_p


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    try:
        n_token = next(data)
    except StopIteration:
        return
    n, m = int(n_token), int(next(data))
    prices = [0] + [int(next(data)) for _ in range(n)]

    graph: list[list[int]] = [[] for _ in range(n + 1)]
    rev_graph: list[list[int]] = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v, t = int(next(data)), int(next(data)), int(next(data))
        graph[u].append(v)
        rev_graph[v].append(u)
        if t == 2:
            graph[v].append(u)
            rev_graph[u].append(v)

    min_p = compute_min_prices(n, prices, graph)
    max_p = compute_max_prices(n, prices, rev_graph)

    best_profit = max((max_p[i] - min_p[i] for i in range(1, n + 1) if min_p[i] <= 100 and max_p[i] >= 0), default=0)
    print(best_profit)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 04:48
 * update_at: 2026-10-05 04:49
 */
#include <bits/stdc++.h>
using namespace std;

// 一本通 3.2 练习 5 最优贸易：正反向 SPFA 预处理前缀最低买入价与后缀最高卖出价
// 数据范围 n <= 1e5，m <= 5e5，价格在 1..100 之间，队列松弛可快速收敛

const int MAXN = 100005;
const int MAXM = 1000005; // m <= 5e5，双向边拆成两条，最多 1e6 条有向边
const int INF = 1e9;

typedef long long ll;

ll n;
ll m;
int price[MAXN]; // price[i] 表示第 i 号城市的水晶球价格，值域只有 1..100，用 int

// 正向图存所有有向边，反向图把每条边方向翻转，用链式前向星避免大 vector 开销
int head[MAXN];
int to[MAXM];
int nxt[MAXM];
int edge_cnt;
int rhead[MAXN];
int rto[MAXM];
int rnxt[MAXM];
int redge_cnt;

int min_buy[MAXN];  // min_buy[i] 表示从 1 号城市走到 i 的路径上出现过的最低价格
int max_sell[MAXN]; // max_sell[i] 表示从 i 号城市走到 n 的路径上出现过的最高价格

// 加入一条有向边 u -> v，正向图和反向图同时登记，省去二次读入
// 城市编号不超过 n <= 1e5，用 int 作端点类型即可
void add_edge(int u, int v) {
    edge_cnt++;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;

    redge_cnt++;
    rto[redge_cnt] = u;
    rnxt[redge_cnt] = rhead[v];
    rhead[v] = redge_cnt;
}

// 正向松弛：沿 1 号城市能走到的边不断更新各点路径上的最低买入价
void spfa_min_buy() {
    for (ll i = 1; i <= n; i++) {
        min_buy[i] = INF;
    }
    min_buy[1] = price[1];

    queue<int> q;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int e = head[u]; e != 0; e = nxt[e]) {
            int v = to[e];
            // 走到 v 时能买到的最低价：之前的最低价与 v 的售价取较小值
            int cand = min_buy[u];
            if (price[v] < cand) {
                cand = price[v];
            }
            if (cand < min_buy[v]) {
                min_buy[v] = cand;
                q.push(v);
            }
        }
    }
}

// 反向松弛：在反向图上从 n 号城市出发，求各点出发能到达 n 时的最高卖出价
void spfa_max_sell() {
    for (ll i = 1; i <= n; i++) {
        max_sell[i] = -1;
    }
    max_sell[n] = price[n];

    queue<int> q;
    q.push(n);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int e = rhead[u]; e != 0; e = rnxt[e]) {
            int v = rto[e];
            // 从 v 出发能卖出的最高价：后续最高价与 v 的售价取较大值
            int cand = max_sell[u];
            if (price[v] > cand) {
                cand = price[v];
            }
            if (cand > max_sell[v]) {
                max_sell[v] = cand;
                q.push(v);
            }
        }
    }
}

// 枚举中转城市 i，把收益拆成 max_sell[i] - min_buy[i]
void solve() {
    spfa_min_buy();
    spfa_max_sell();

    int ans = 0; // 赚不到差价时不做贸易，收益为 0
    for (ll i = 1; i <= n; i++) {
        // min_buy[i] <= 100 说明 i 可由 1 到达，max_sell[i] >= 0 说明 i 可到达 n
        if (min_buy[i] <= 100 && max_sell[i] >= 0) {
            int profit = max_sell[i] - min_buy[i];
            if (profit > ans) {
                ans = profit;
            }
        }
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        cin >> price[i];
    }
    for (ll i = 1; i <= m; i++) {
        int x; // 道路端点，x, y <= n <= 1e5
        int y;
        int z; // z = 1 单向，z = 2 双向
        cin >> x >> y >> z;
        add_edge(x, y);
        if (z == 2) {
            add_edge(y, x); // 双向道路相当于两条方向相反的单向边
        }
    }

    solve();

    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(k(n + m))$ 。图中有 $n \leqslant 10^5$ 个城市， $m \leqslant 5 \times 10^5$ 条边。由于商品价格取值范围在 $[1, 100]$ 内，每个节点的价格只会被单调松弛常数次，队列松弛（SPFA 机制）能够极其迅速地收敛，实际运行时间在 0.1 秒内。
空间复杂度： $\mathcal{O}(n + m)$ 。用于存储正向图与反向图的邻接表，以及正反向极值数组与辅助队列。

总结

本题的关键在于拆分与中转点枚举：

将路径两点的关联最优化问题，转化为以中间点 $i$ 为枢纽的前后两段独立极值问题。
逆向思维：将“从 $i$ 到 $n$ 的最大值”通过反向建图转化为“从 $n$ 出发到达各点的最大值”。
状态转移虽然建立在可能有环的有向图上，但松弛操作具备严格单调性且值域极小，利用 SPFA / 队列松弛能高效求解。

【题目描述】

C 国有n 个大城市和m 条道路，每条道路连接这n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行的道路，一部分为双向通行的道路，双向通行的道路在统计条数时也计为1 条。

C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设C 国n 个城市的标号从1~ n，阿龙决定从1 号城市出发，并最终在n 号城市结束自己的旅行。在旅游的过程中，任何城市可以重复经过多次，但不要求经过所有n 个城市。阿龙通过这样的贸易方式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来C 国旅游，他决定这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。

假设 C 国有5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路为单向通行，双向箭头表示这条道路为双向通行。

假设 1~n 号城市的水晶球价格分别为4，3，5，6，1。阿龙可以选择如下一条线路：1->2->3->5，并在2 号城市以3 的价格买入水晶球，在3号城市以5 的价格卖出水晶球，赚取的旅费数为2。

阿龙也可以选择如下一条线路 1->4->5->4->5，并在第1 次到达5 号城市时以1 的价格买入水晶球，在第2 次到达4 号城市时以6 的价格卖出水晶球，赚取的旅费数为5。

现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。

【输入】

第一行包含 2 个正整数n 和m，中间用一个空格隔开，分别表示城市的数目和道路的数目。

第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这n 个城市的商品价格。

接下来 m 行，每行有3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，表示这条道路是城市x 到城市y 之间的单向道路；如果z=2，表示这条道路为城市x 和城市y 之间的双向道路。

【输出】

共1 行，包含1 个整数，表示最多能赚取的旅费。如果没有进行贸易，则输出0。

【输入样例】

text

【输出样例】

text

【提示】

【数据范围】

输入数据保证 1 号城市可以到达n 号城市。

对于 10%的数据，1≤n≤6。

对于 30%的数据，1≤n≤100。

对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。

对于 100%的数据，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市水晶球价格≤100。

【来源】

一本通在线评测

「一本通 3.2 练习 5」最优贸易

目录

形式化题目

正解

思路

代码

复杂度

总结