GESP 题解库 / 7 级题解 / [GESP202312 七级] 商品交易 · 第 20 / 24 题
GESP202312 七级 · P10110 · 中等

商品交易

交换 x → y 的花费是 v_y − v_x + 1;求从商品 a 换到 b 的最小花费(可以为负)。

📦
N ≤ 10⁵, M ≤ 2 × 10⁵
商品数与商人数
🔢
long long
花费可能为负
⚡
O(N + M)
时间复杂度
🎯
换元 g = d − v + BFS
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

市场上有 N 种商品(编号 0 … N − 1),第 i 种商品价值 vᵢ 元。共有 M 个商人,第 j 个商人处可以用第 xⱼ 种商品换第 yⱼ 种商品。

交易按商品价值结算:若 v_{xⱼ} > v_{yⱼ},商人付给你 v_{xⱼ} − v_{yⱼ} 元;否则你要付给商人 v_{yⱼ} − v_{xⱼ} 元。此外每次交易商人都要收 1 元手续费,不论价值孰高孰低。

你现在持有商品 a,希望通过若干次交换得到商品 b。求至少需要花多少钱(最小花费可能是负数,表示你在完成目标的同时还赚了钱)。如果无法换到商品 b,输出 No solution。

输入:第一行 N、M、a、b;第二行 v₀ … v_{N−1};随后 M 行,每行 xⱼ yⱼ。

💡
人话翻译:把商品看成点,"用 x 换 y"看成一条有向边 x → y,这条边的花费是 v_y − v_x + 1。
问题就是"从 a 到 b 的最短路"。但边权可能为负(价值暴跌时商人会倒找你钱),所以不能直接用 Dijkstra。
妙处在于换元:令 d[i] 表示"换到商品 i 的最小花费",再令 g[i] = d[i] − v_i,于是每次交换恰好让 g 增加 1:g[y] = g[x] + 1。
又因为 g[a] = d[a] − v_a = −v_a,所以 g[b] = −v_a + ℓ,其中 ℓ 是路径上的交换次数;于是 d[b] = v_b − v_a + ℓ。
结论:最小化花费 ⟺ 最小化交换次数,也就是在一张无权图上求最短路 ——直接 BFS!

🔍 关键词提取

有向图最短路负权边换元(势能函数)无权图 BFS

已知条件

项目说明
输入第一行 N、M、a、b;第二行 v₀ … v_{N−1};之后 M 行每行 xⱼ yⱼ
输出最小花费;无法换到 b 则输出 No solution
数据范围N ≤ 10⁵,M ≤ 2 × 10⁵,1 ≤ vᵢ ≤ 10⁹
交易花费用 x 换 y:先按差价结算(可为负),再交 1 元手续费
边的方向有向边 x → y(用 x 换 y,不能反向)
约束a ≠ b,xⱼ ≠ yⱼ

需要解决的问题

02
思维导图
整理解题思路的全貌
📦 最小花费 = v_b − v_a + 最少交换次数
🧠 换元
d[i]:换到商品 i 的最小花费
g[i] = d[i] − v_i
交换 x → y 后 g[y] = g[x] + 1
g[a] = −v_a(因为 d[a] = 0)
📐 望远镜求和
一条路径的花费 = Σ(v_y − v_x + 1)
= v_b − v_a + ℓ
中途商品的价值全部抵消
ℓ 就是路径上的交换次数
🔎 最小化什么
花费只与 ℓ 有关(首尾价值是常数)
所以要 ℓ 最小 = 最少交换次数
无权图最短路 = BFS
dist[b] 就是 ℓ
⚠️ 易错点
用 Dijkstra(有负权边,会错)
用 SPFA(最坏会被卡超时)
把有向边建成无向边
b 不可达时忘记输出 No solution
03
样例手算推导
三个样例的完整推演

🧮 样例 1:N = 3, M = 5, a = 0, b = 2,答案 5

数据:v = [1, 2, 4];边为 1→0、2→0、0→1、2→1、1→2。

1
先 BFS 求最少交换次数

dist[0] = 0(起点)

从 0 出发:0 → 1,dist[1] = 1

从 1 出发:1 → 2,dist[2] = 2

所以 ℓ = dist[2] = 2

✅ ℓ = 2

2
再算花费(逐步模拟)

第 1 步:用商品 0(价值 1)换商品 1(价值 2)

付差价 2 − 1 = 1 元,加手续费 1 元,共 2 元

第 2 步:用商品 1(价值 2)换商品 2(价值 4)

付差价 4 − 2 = 2 元,加手续费 1 元,共 3 元

累计 2 + 3 = 5 元

✅ 5

用公式核对:v₂ − v₀ + ℓ = 4 − 1 + 2 = 5 ✓

🔑
望远镜求和看得很清楚:(2 − 1 + 1) + (4 − 2 + 1) = 2 + 3 = 5,其中中间商品的价值 2 被"减一次、加一次"抵消掉了,结果恰好是 v₂ − v₀ + 2。
这就是"换元"的几何意义:把每种商品的价值从边权里"提"出来,边权就只剩常数 1。

🧮 样例 2 与样例 3:花费为负 / 为什么无解

样例 2 数据:N = 3, M = 3, a = 0, b = 2,v = [100, 2, 4],边为 0→1、1→2、0→2。

1
样例 2:直接换最划算

BFS:dist[1] = 1,dist[2] = 1(有直接边 0 → 2)

所以 ℓ = 1,花费 = v₂ − v₀ + 1 = 4 − 100 + 1 = −95

另一条路 0 → 1 → 2 要走 2 步:

花费 = 4 − 100 + 2 = −94 > −95,更差

✅ −95(净赚 95 元)

2
样例 3:不可达

数据:N = 4, M = 4, a = 3, b = 0,v = [1, 2, 3, 4]

边为 1→0、0→1、3→2、2→3

BFS:从 3 只能到 2(dist[3] = 0, dist[2] = 1),

再走回 3,仍然在 {2, 3} 这个连通块里打转

dist[0] 始终是 −1 → 换不到商品 0

✅ No solution

样例最短交换次数 ℓv_b − v_a最小花费说明
2(走 0→2)14 − 100 = −96−95价值暴跌 → 倒赚
2(走 0→1→2)2−96−94步数多一步,就多花 1 元
3不可达3 − 4 = −1No solution两个连通块互不相通
⚠️
注意"花费可以为负"这件事:它不会破坏算法——因为我们的公式 v_b − v_a + ℓ 里 v_b − v_a 本来就可正可负。
真正会破坏算法的是"负边权":如果你绕过换元、直接拿 v_y − v_x + 1 当边权跑 Dijkstra,就会在负权边上出错。而换元之后,"边权"变成了统一的 1,负值全部被吸收进常数项,问题彻底变干净。
04
解法对比
换元 + BFS vs SPFA / Dijkstra

⚔️ 解法对比

🟢 换元 + BFS(推荐) 推荐

g[i] = d[i] − v_i 后每条边让 g 恰好加 1,于是只需求"最少交换次数"

  • 时间 O(N + M) = 3 × 10⁵
  • 一趟 BFS 解决,常数极小
  • 代码约 25 行
  • 天然处理负花费
💡
换元为什么这么灵?边权里混着"商品价值",而价值沿着路径会首尾相消;换元就是把这份"势能"从边权里提出来,让剩下的部分变成常数 1。于是带权最短路退化成无权最短路。

🟠 SPFA / Bellman-Ford

把边权看成 v_y − v_x + 1,硬做带权最短路

  • 确实能处理负权边
  • 最坏 O(NM) = 2 × 10¹⁰
  • 容易被特殊数据卡超时
  • 白白浪费了题目的结构
⚠️
两条路都不必走:Dijkstra 因为负权边不适用;SPFA 虽然能处理负权,但最坏会被卡到超时。本题的最优解是"换元 + BFS"。

📈 性能对比

方案复杂度可行性
换元 + BFSO(N + M) = 3 × 10⁵✅ 稳过
SPFA最坏 O(NM) = 2 × 10¹⁰❌ 可能被卡
Dijkstra—❌ 存在负权边,结论错误
05
算法流程图
换元后 BFS 求最少交换次数
开始读入 N、M、a、b、v[] 与 M 条有向边 x → y;建邻接表dist[] 全部置 −1,dist[a] = 0,a 入队队列不空(BFS 逐层扩展)取出队首 u,遍历它的每条出边 u → ww 还没被访问过吗(dist[w] == −1)?是 ✓dist[w] = dist[u] + 1,把 w 入队否 ✗跳过:已经用更少的步数到达过 w所有可达点都访问完了吗?dist[b] 是否为 −1?是 ✗换不到商品 b,输出 No solution否 ✓输出 v_b − v_a + dist[b]输出答案继续 BFS 下一层
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

📦 最小花费计算器

第一行 N M a b;第二行 v 数组(N 个数);随后 M 行每行 x y(用 x 换 y)。程序做 BFS 并给出最短交换路径。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(换元 + BFS)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M, a, b;
    scanf("%d %d %d %d", &N, &M, &a, &b);

    vector<long long> v(N);
    for (int i = 0; i < N; i++) scanf("%lld", &v[i]);

    vector<vector<int>> adj(N);
    for (int j = 0; j < M; j++) {
        int x, y;
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);          // 有向边:用 x 换 y
    }

    // 无权图 BFS:dist[i] = 从 a 出发到 i 的"最少交换次数"
    vector<int> dist(N, -1);
    queue<int> q;
    dist[a] = 0;
    q.push(a);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int w : adj[u]) {
            if (dist[w] == -1) {      // 每个点只入队一次 → O(N + M)
                dist[w] = dist[u] + 1;
                q.push(w);
            }
        }
    }

    if (dist[b] == -1) puts("No solution");
    else printf("%lld\n", v[b] - v[a] + (long long)dist[b]);
    return 0;
}
🔑
为什么答案是 v[b] − v[a] + dist[b]?一条路径的总花费是Σ (v_y − v_x + 1),相邻项里中间商品的价值一加一减正好抵消,只剩下 v_b − v_a 再加上"交换了多少次"(每次贡献 1 元手续费)。
所以 dist[b](最少交换次数)就是这里要的 ℓ。

📖 关键几行怎么看

代码作用为什么这样写
adj[x].push_back(y)建有向边用 x 换 y 是单向的,千万别建成双向
dist[a] = 0; q.push(a)BFS 起点你手上的商品 a 是一切交换的出发点
if (dist[w] == -1) { dist[w] = dist[u] + 1; }无权最短路核心第一次访问即最优(每层代价都是 1)
dist[b] == -1无解判定b 从未被访问 → 换不到 → 输出 No solution
v[b] - v[a] + dist[b]答案公式望远镜求和的结果,恰是"最少花费"
⚠️
五个坑:① 把有向边建成无向边(题意是"用 x 换 y");② 用 Dijkstra 求带权最短路(负权边会让它出错);③ 用 SPFA 硬刚(最坏 O(NM),可能超时);④ 忘记输出 No solution;⑤ 用 int 存答案:v 最大 10⁹,v_b − v_a 可达 ±10⁹,再加上 M 的偏移,必须用 long long。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
3 5 0 2
1 2 4
1 0 / 2 0 / 0 1 / 2 1 / 1 2
5题面样例 1(v₂ − v₀ + 2 = 5)
3 3 0 2
100 2 4
0 1 / 1 2 / 0 2
−95题面样例 2(花费为负 = 倒赚)
4 4 3 0
1 2 3 4
1 0 / 0 1 / 3 2 / 2 3
No solution题面样例 3(两个连通块,互不相通)
2 1 0 1
5 5
0 1
1价值相同:只剩 1 元手续费
2 1 0 1
100 1
0 1
−98价值暴跌:倒赚 99 元,再交 1 元手续费
4 4 0 3
10 20 30 40
0 3 / 0 1 / 1 2 / 2 3
31两条路(1 步 vs 3 步),选边数少的
✅
自查清单:① 有向边建对了吗?② 用的是 BFS(而不是 Dijkstra)吗?③ 判了 No solution 吗?④ 答案用了 long long 吗?

🚨 易错点清单

⚠️
建成无向边:题意是"用 x 换 y",只有 x → y 这一条方向。
⚠️
用 Dijkstra:边权 v_y − v_x + 1 可能为负,Dijkstra 会给出错误结果。
⚠️
漏判无解:dist[b] == −1 时必须输出 No solution,不能输出某个数字。
⚠️
用 int 存花费:价值可达 10⁹,差值加上步数会溢出 int。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N + M)
空间复杂度
O(N + M)
N, M 最大
10⁵, 2 × 10⁵
运算量
约 3 × 10⁵

时间怎么算的?

空间都用在哪?

邻接表约 2 × 10⁵ 条边 + dist 数组 10⁵ 个 int + v 数组 10⁵ 个 long long。

✅ 约 30 万次操作,瞬间完成。换元把"带权最短路"变成了"无权最短路",这才是本题真正的考点——而不是写一个能处理负权的最短路算法。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 一条路径的总花费 = v_b − v_a + 交换次数(中途价值全部抵消)
//   (v_{u1} − v_{u0} + 1) + (v_{u2} − v_{u1} + 1) + … + (v_{uℓ} − v_{uℓ−1} + 1)
//   = v_b − v_a + ℓ

// 换元:令 g[i] = d[i] − v_i
//   交换 x → y 时 d[y] = d[x] + (v_y − v_x + 1)
//   代入得         g[y] = g[x] + 1        <-- 每条边都恰好让 g 加 1
//   又 g[a] = d[a] − v_a = −v_a
//   所以 g[b] = −v_a + ℓ   ==>   d[b] = v_b − v_a + ℓ

// 最小化 d[b]  <=>  最小化 ℓ  <=>  无权图最短路  <=>  BFS
dist[a] = 0; q.push(a);
while (!q.empty()) {
    int u = q.front(); q.pop();
    for (int w : adj[u])
        if (dist[w] == -1) { dist[w] = dist[u] + 1; q.push(w); }
}
if (dist[b] == -1) puts("No solution");
else printf("%lld\n", v[b] - v[a] + dist[b]);

// 通用思想:如果边权能写成 w(x → y) = φ(y) − φ(x) + c
// (本题 φ = 商品价值,c = 1),那么"路径代价"只与边数有关,
// 于是带权最短路退化为无权最短路,直接 BFS。

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
换元(势能函数)把 d[i] − v_i 当成新变量,边权化为常数 1边权形如 φ(y) − φ(x) + c 的最短路、差分约束
望远镜求和路径花费只看首尾价值 + 边数差分、前缀和、路径长度无关中间量的计数
无权最短路 BFS求"最少交换次数"最少步数、最少操作次数、最少跳数类问题
🌟
思考题:如果每个商人收的手续费不再是固定的 1 元,而是"用第 j 个商人交易一次收 fⱼ 元"(每条边各自的钱),换元还能把问题变成 BFS 吗?(提示:不能了——此时路径花费是 v_b − v_a + Σf,需要按边权 fⱼ 求最短路;只要 fⱼ ≥ 0 就可以用 Dijkstra,但"每条边权重不同"让 BFS 不再适用。所以"手续费恰好是常数 1"才是本题能用 BFS 的关键前提。)