商品交易题解

题目分析

我们有 $N$ 种商品，每种商品有一个价值 $v_i$ 。 $M$ 个商人各自提供一次单向交换机会：可以用手中的第 $x_j$ 种商品交换商人手上的第 $y_j$ 种商品。每次交换的规则如下：

无论商品价值高低，都需要支付 $1$ 元手续费；
如果 $v_{x_{j}} > v_{y_{j}}$ ，商人补给我们差价 $v_{x_j} - v_{y_j}$ ；
如果 $v_{x_j} \le v_{y_j}$ ，我们需要补给商人差价 $v_{y_j} - v_{x_j}$ 。

现在你初始拥有商品 $a$ ，目标是获得商品 $b$ ，求最少花费（可以是负数，表示赚钱）。

我们可以把每次交换的花费统一表示。从商品 $u$ 交换到商品 $v$ 时：

手续费： $+1$
价值差：无论哪种情况，商人实际给我们的钱是 $v_u - v_v$ ？再想一想：如果 $v_{u} > v_{v}$ ，商人付给我们 $v_u - v_v$ ，即我们收入 $v_u - v_v$ ，花费为 $-(v_u - v_v) = v_v - v_u$ ；如果 $v_u \le v_v$ ，我们付给商人 $v_v - v_u$ ，花费为 $v_v - v_u$ 。因此每次交换的净花费总是：

cos t (u \to v) = 1 + (v_{v} - v_{u})

这个公式非常简洁，与 $v_u$ 和 $v_v$ 的大小关系无关。

现在，我们要从商品 $a$ 出发，经过一系列中间商品 $c_1, c_2, \dots, c_k$ ，最终到达 $b$ ，即路径：

a \to c_{1} \to c_{2} \to \dots \to c_{k} \to b

总花费为：

t o t a l = (1 + v_{c_{1}} - v_{a}) + (1 + v_{c_{2}} - v_{c_{1}}) + \dots + (1 + v_{b} - v_{c_{k}}) = k + 1 + (v_{b} - v_{a}) = 路径上的边数 + v_{b} - v_{a}

神奇的事情发生了：所有中间商品的价值全部抵消，总花费只与经过的商人数（边数）以及起点和终点的价值有关。因此，要最小化总花费，我们只需要最小化从 $a$ 到 $b$ 的最少交换次数（即图上的最短路径长度）。

解题思路

将问题转化为图论模型：

节点： $N$ 种商品，编号 $0 \sim N-1$ 。
有向边：对于每个商人给出的交换 $(x_j, y_j)$ ，连一条从 $x_j$ 指向 $y_j$ 的单向边。
边权：根据推导，所有边的等价权值都是 $1$ （每走一步增加一次手续费，商品价值抵消）。

那么，从 $a$ 到 $b$ 的最小花费 $= \text{dist}(a, b) + v_b - v_a$ ，其中 $\text{dist}(a, b)$ 是 $a$ 到 $b$ 的最短路径长度（如果不可达则无解）。

因为每条边权都是 $1$ ，我们可以使用**广度优先搜索（BFS）**来求最短路，时间复杂度 $O(N+M)$ 。

最后判断：如果 BFS 结束后 $b$ 的距离仍为初始化的无穷大，说明无法到达，输出 No solution；否则输出 $dist[b] + v_b - v_a$ 。

算法说明

读入 $N, M, a, b$ 。
读入 $N$ 个价值 $v_0 \dots v_{N-1}$ 。
建立邻接表 vector<int> edge[N]，对每个商人 $(x, y)$ ，执行 edge[x].push_back(y)。
初始化距离数组 dist 为 $-1$ 或一个很大的数（表示未访问），将起点 $a$ 的距离设为 $0$ ，入队。
进行 BFS：
- 取出队首 $u$ ，遍历 $u$ 的出边 $v$ ；
- 若 $dist[v]$ 未访问，则 $dist[v] = dist[u] + 1$ ，并将 $v$ 入队。
检查 $dist[b]$ $d i s t [b]$ ：
- 若为未访问状态，输出 No solution；
- 否则输出 $dist[b] - v_a + v_b$ （注意运算顺序避免溢出，long long 即可）。

复杂度分析

建图： $O(M)$ 。
BFS：每个节点最多入队一次，每条边访问一次， $O(N+M)$ 。
总时间复杂度： $O(N+M)$ ，在 $N \le 10^5, M \le 2\times 10^5$ 的范围内可以轻松通过。
空间复杂度：存储邻接表 $O(N+M)$ 。

代码实现与说明

下面是基于上述思路的 C++ 实现（参考代码的精简版，并添加了注释）：

cpp
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <cstring>  // memset
5using namespace std;
6
7const int MAXN = 100010;
8int n, m, a, b;
9long long val[MAXN];          // 商品价值
10vector<int> edge[MAXN];       // 邻接表
11int dist[MAXN];               // 最短距离（边数）
12
13void bfs(int start) {
14    memset(dist, -1, sizeof(dist)); // -1 表示未访问
15    queue<int> q;
16    q.push(start);
17    dist[start] = 0;
18    while (!q.empty()) {
19        int u = q.front(); q.pop();
20        for (int v : edge[u]) {
21            if (dist[v] == -1) {    // 未访问过
22                dist[v] = dist[u] + 1;
23                q.push(v);
24            }
25        }
26    }
27}
28
29int main() {
30    ios::sync_with_stdio(false);
31    cin.tie(nullptr);
32    
33    cin >> n >> m >> a >> b;
34    for (int i = 0; i < n; ++i) cin >> val[i];
35    for (int i = 0; i < m; ++i) {
36        int x, y;
37        cin >> x >> y;
38        edge[x].push_back(y);   // 单向边
39    }
40    
41    bfs(a);
42    
43    if (dist[b] == -1) {
44        cout << "No solution\n";
45    } else {
46        // 总花费 = 边数 + v_b - v_a
47        // 注意 val 是 long long 防止运算溢出
48        long long ans = dist[b] + val[b] - val[a];
49        cout << ans << '\n';
50    }
51    return 0;
52}

代码细节说明

使用 memset(dist, -1, sizeof(dist)) 初始化距离数组，既清晰又能方便判断未访问。
BFS 时利用 queue<int> 进行层序遍历，保证首次访问的路径一定是最短的。
价值 val 与答案 ans 使用 long long，因为商品价值最高可达 $10^9$ ，路径长度最大为 $10^5$ ，运算结果可能超出 int 范围（尽管题目输出看似 int 能存，但安全起见用 long long）。
快速 IO（ios::sync_with_stdio(false)）可以应对百万级别的输入。

总结

本题的关键在于推导出每次交换花费的统一公式 $1 + v_v - v_u$ ，从而将问题转化为求 $a$ 到 $b$ 的最少交换次数。一旦抓住这一点，剩下的就是简单的 BFS 求无权图最短路。类似的问题在竞赛中常以「等价转换」的形式出现，需要选手细心分析花费的构成。

题库

题库

12971.商品交易

题解大全共 1 篇