2023年12月GESP真题及题解(C++七级): 商品交易

2023年12月GESP真题及题解(C++七级): 商品交易

题目描述

市场上共有N NN种商品，编号从0 00至N − 1 N-1N−1，其中，第i ii种商品价值v i v_ivi​元。

现在共有M MM个商人，编号从0 00至M − 1 M-1M−1。在第j jj个商人这，你可以使用你手上的第x j x_jxj​种商品交换商人手上的第y j y_jyj​种商品。每个商人都会按照商品价值进行交易，具体来说，如果v x j > v y j v_{x_j}>v_{y_j}vxj​​>vyj​​，他将会付给你v x j − v y j v_{x_j}-v_{y_j}vxj​​−vyj​​元钱；否则，那么你需要付给商人v y j − v x j v_{y_j}-v_{x_j}vyj​​−vxj​​元钱。除此之外，每次交易商人还会收取1 11元作为手续费，不论交易商品的价值孰高孰低。

你现在拥有商品a aa，并希望通过一些交换来获得商品b bb。请问你至少要花费多少钱？（当然，这个最小花费也可能是负数，这表示你可以在完成目标的同时赚取一些钱。）

输入格式

第一行四个整数N , M , a , b N , M , a , bN,M,a,b，分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证0 ≤ a , b < N 0 \le a,b < N0≤a,b<N，保证a ≠ b a \ne ba=b。

第二行N NN个用单个空格隔开的正整数v 0 , v 1 , … , v N − 1 v_0,v_1,…,v_{N-1}v0​,v1​,…,vN−1​，依次表示每种商品的价值。保证1 ≤ v i ≤ 10 9 1≤v_i≤10^91≤vi​≤109。

接下来M MM行，每行两个整数x j , y j x_j,y_jxj​,yj​，表示在第j jj个商人这，你可以使用第x j x_jxj​种商品交换第y j y_jyj​种商品。保证0 ≤ x j , y j < N 0≤x_j,y_j<N0≤xj​,yj​<N，保证x j ≠ y j x_j≠y_jxj​=yj​。

输出格式

输出一行一个整数，表示最少的花费。特别地，如果无法通过交换换取商品b bb，请输出No solution。

输入输出样例 1

输入 1

3 5 0 2 1 2 4 1 0 2 0 0 1 2 1 1 2

输出 1

5

输入输出样例 2

输入 2

3 3 0 2 100 2 4 0 1 1 2 0 2

输出 2

-95

输入输出样例 3

输入 3

4 4 3 0 1 2 3 4 1 0 0 1 3 2 2 3

输出 3

No solution

说明/提示

数据范围

对于30%的测试点，保证N ≤ 10 N ≤ 10N≤10，M ≤ 20 M ≤ 20M≤20。

对于70%的测试点，保证N ≤ 10 3 N ≤10^3N≤103，M ≤ 10 4 M≤10^4M≤104。

对于100%的测试点，保证N ≤ 10 5 N≤10^5N≤105，M ≤ 2 × 10 5 M≤2×10^5M≤2×105。

思路分析

这个问题可以转化为图论中的最短路径问题。核心思路是：

1. 问题建模

• 将每种商品看作图中的节点
• 将商人提供的交换关系看作有向图的边
• 边的权重（花费） =abs(v[x] - v[y]) + 1
  • abs(v[x] - v[y])：商品差价
  • +1：固定的手续费

2. 特殊处理：负权边

由于交易可能赚钱（即花费为负），所以图中存在负权边。因此不能使用普通的Dijkstra算法，需要使用能处理负权的最短路径算法。

3. 算法选择

• SPFA算法：适用于有负权边的图，最坏时间复杂度O(VE)，但实际运行较快
• Bellman-Ford算法：更稳定，但时间复杂度O(VE)，在本题数据范围下可能超时
• 本题选择SPFA，并加入负环检测

4. 负环处理

如果图中存在负环，且起点a能到达负环，且从负环能到达终点b，那么理论上可以通过无限次交易赚取无限多的钱，最小花费是负无穷。但题目未明确说明这种情况，我们按常规处理：如果检测到负环且能到达b，则输出"No solution"（因为这种情况在实际中不可能实现无限次交易）。

代码实现

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;// 使用long long防止数据溢出constll INF=1e18;// 定义无穷大值constintMAXN=1e5+10;// 最大商品数量intn,m,a,b;// n:商品数, m:商人数, a:起点商品, b:目标商品ll v[MAXN];// v[i]:第i种商品的价值vector<pair<int,ll>>g[MAXN];// 邻接表存储图，g[u] = {(v, w)}表示从u到v的边，权重为w/** * SPFA算法求最短路径 * ans 输出参数，存储计算得到的最小花费 * 返回值：true:找到解，false:无解（不可达或存在负环） */boolspfa(ll&ans){// d[i]:从起点a到商品i的最小花费vector<ll>d(n,INF);// cnt[i]:节点i入队次数，用于检测负环vector<int>cnt(n,0);// inq[i]:节点i是否在队列中vector<bool>inq(n,false);// 队列用于存储待处理的节点queue<int>q;// 初始化起点d[a]=0;q.push(a);inq[a]=true;cnt[a]=1;// SPFA主循环while(!q.empty()){intu=q.front();// 取出队首节点q.pop();inq[u]=false;// 标记为不在队列中// 遍历节点u的所有出边for(auto&e:g[u]){intto=e.first;// 目标节点ll w=e.second;// 边权（交易花费）// 松弛操作：如果通过u到达to的距离更短，则更新if(d[u]+w<d[to]){d[to]=d[u]+w;// 更新最短距离// 如果to不在队列中，加入队列if(!inq[to]){q.push(to);inq[to]=true;cnt[to]++;// 入队次数+1// 负环检测：如果一个节点入队超过n次，说明存在负环// 在负环中可以无限减少花费，这种情况视为无解if(cnt[to]>n){returnfalse;// 存在负环，返回无解}}}}}// 检查是否可达目标商品bif(d[b]==INF){returnfalse;// 不可达，返回无解}// 将结果赋值给输出参数ans=d[b];returntrue;// 成功找到最短路径}intmain(){// 加速输入输出ios::sync_with_stdio(false);cin.tie(0);// 读入基本参数cin>>n>>m>>a>>b;// 读入商品价值for(inti=0;i<n;i++){cin>>v[i];}// 建立交易关系图for(inti=0;i<m;i++){intx,y;cin>>x>>y;// 计算交易花费：v[y] - v[x] + 1// 公式推导：// 1. 如果v[x] > v[y]：我们得到(v[x]-v[y])元差价，支付1元手续费// 总花费 = -(v[x]-v[y]) + 1 = v[y] - v[x] + 1（负花费表示赚钱）// 2. 如果v[x] < v[y]：我们支付(v[y]-v[x])元差价，支付1元手续费// 总花费 = v[y] - v[x] + 1// 两种情况统一为：花费 = v[y] - v[x] + 1ll cost=v[y]-v[x]+1;// 添加有向边：从商品x到商品y，权重为cost// 注意：交易是单向的，只能使用x交换yg[x].push_back({y,cost});}// 调用SPFA算法计算最小花费ll ans;if(spfa(ans)){cout<<ans<<"\n";// 输出最小花费}else{cout<<"No solution\n";// 无解输出}return0;}

功能分析

1. 算法设计思路

图建模

• 将每种商品视为图中的节点
• 将商人提供的交易关系视为有向边
• 边的权重计算公式：v[y] - v[x] + 1
  • v[y] - v[x]: 商品价值差
  • +1: 固定手续费

算法选择

• 由于存在负权边（当v[y] < v[x]时），不能使用Dijkstra算法
• 选择SPFA (Shortest Path Faster Algorithm)算法
  • 本质是Bellman-Ford算法的队列优化版本
  • 能处理负权边
  • 平均时间复杂度优于Bellman-Ford

2. 核心功能模块

数据结构

1. 邻接表 (g[MAXN]):

   • 存储图结构
   • 每个元素为pair<int, ll>，表示(目标节点, 边权重)
   • 空间复杂度: O(N+M)

2. 距离数组 (d[n]):

   • 存储从起点a到每个节点的最短距离
   • 初始值为INF（无穷大）

3. 辅助数组:

   • cnt[n]: 记录节点入队次数，用于负环检测
   • inq[n]: 标记节点是否在队列中，避免重复入队

SPFA算法流程

1. 初始化: 起点距离为0，加入队列
2. 循环处理队列:
   • 取出队首节点u
   • 遍历u的所有出边
   • 尝试松弛操作：如果通过u到达邻居的距离更短，则更新
   • 如果邻居被更新且不在队列中，则加入队列
3. 负环检测: 如果一个节点入队超过n次，说明存在负环
4. 结果判断: 如果目标节点b的距离仍为INF，说明不可达

3. 关键点说明

负权边处理

• 边权公式v[y] - v[x] + 1可能为负值
• 负权边表示交易可以赚钱（获得差价大于手续费）
• SPFA算法能正确处理负权边

负环检测

• 负环: 环上所有边的权重之和为负数
• 影响: 在负环上可以无限循环交易，无限减少花费
• 处理: 检测到负环则视为无解，返回"No solution"

不可达判断

• 初始化所有节点距离为INF
• 如果经过算法后b的距离仍为INF，说明从a无法到达b
• 返回"No solution"

4. 时间复杂度分析

理论复杂度

• 最坏情况: O(VE) = O(2×10^10)
• 平均情况: 远好于最坏情况
• 实际表现: 在本题数据范围内通常可以接受

优化特点

1. 队列优化: 只处理距离发生变化的节点
2. 避免冗余: 使用inq数组防止重复入队
3. 提前终止: 检测到负环时提前返回

5. 空间复杂度分析

• 邻接表: O(N+M) ≈ 3×10^5
• 辅助数组: O(N) ≈ 10^5
• 总空间: 约1.6MB，远小于内存限制

6. 边界情况处理

数据类型

• 使用long long存储距离，防止溢出
• 商品价值最大109 ^99，M最大2×105 ^55
• 最坏情况下总花费可能超过int范围

特殊输入

1. 无解情况:

   • 不可达（无交易路径）
   • 存在负环且能到达目标

2. 零花费/赚钱情况:

   • 最小花费为负数表示交易赚钱
   • 算法能正确处理负距离

完整GESP C++考级真题题解专栏：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

更多csp信奥赛C++学习资料汇总：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

4、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}