【数据结构OJ】【图论】货币套汇(图路径)

devtools/2024/11/24 13:44:16/

题目描述

套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如,假定1 美元可以买0.7 英镑,1 英镑可以买9.5 法郎,1法郎可以买到0.16美元。通过货币兑换,一个商人可以从1 美元开始买入,得到0.7×9.5×0.16=1.064美元,从而获得6.4%的利润。 给定n种货币c1 ,c2 ,... ,cn的有关兑换率,试设计一个有效算法,确定货币间是否存在套汇的可能性。

提示:判断图上是否出现正环,即环上所有的边相乘大于1

输入

第一行:测试数据组数

每组测试数据格式为:

第一行:正整数n (1< =n< =30),正整数m,分别表示n种货币和m种不同的货币兑换率。

2~n+1行,n种货币的名称。

n+2~n+m+1行,每行有3 个数据项ci,rij 和cj ,表示货币ci 和cj的兑换率为 rij。

输出

对每组测试数据,如果存在套汇的可能则输出YES

如果不存在套汇的可能,则输出NO。

IO模式

本题IO模式为标准输入/输出(Standard IO),你需要从标准输入流中读入数据,并将答案输出至标准输出流中

输入样例

2
3 3
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3 6
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

输出样例

YES
NO

注意的就是加一个visit数组标记访问过的元素防止代码陷入死循环就行了、

#include <iostream>
#include <string>
using namespace std;
int search(int start, int j, int n, double hl, double **a, int visit[]) {if (j == start) {if (hl > 1) {return 1;} else {return 0;}}int tag = 0;for (int i = 0; i < n; i++) {if (a[j][i] != 0 && visit[i] == 0) {visit[i] = 1;tag = search(start, i, n, hl * a[j][i], a, visit);visit[i] = 0;}if (tag == 1) {return tag;}}return tag;
}
int main() {int t;cin >> t;while (t--) {int n, m;cin >> n >> m;string name[n];for (int i = 0; i < n; i++) {cin >> name[i];}double **a = new double*[n];for (int i = 0; i < n; i++) {a[i] = new double[n];}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {a[i][j] = 0;}}string n1, n2;double hl;for (int i = 0; i < m; i++) {cin >> n1 >> hl >> n2;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (name[i] == n1 && name[j] == n2) {a[i][j] = hl;}}}}int tag = 0;int visit[n];for (int i = 0; i < n; i++) {visit[i] = 0;}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (a[i][j] != 0) {visit[j] = 1;tag = search(i, j, n, a[i][j], a, visit);visit[j] = 0;}if (tag == 1) {break;}}if (tag == 1) {break;}}if (tag == 1) {cout << "YES" << endl;} else {cout << "NO" << endl;}}
return 0;
}


http://www.ppmy.cn/devtools/136562.html

相关文章

Python 编程开发(01):Bash 命令行基本操作

Bash 是一种功能强大的 shell 语言&#xff08;或命令行语言&#xff09;&#xff0c;广泛用于 Unix 和 Unix-like 操作系统&#xff0c;如 Linux 和 macOS。它提供了一个交互式界面&#xff0c;允许用户输入命令以执行各种操作&#xff0c;如文件管理、程序执行、网络配置等。…

用邻接矩阵实现图的深度优先遍历

问题描述 给定一个无向图&#xff0c;用邻接矩阵作为图的存储结构&#xff0c;输出指定顶点出发的深度优先遍历序列。在深度优先遍历的过程中&#xff0c;如果同时出现多个待访问的顶点&#xff0c;则优先选择编号最小的一个进行访问。 输入描述 第一行输入三个正整数&#…

汽车免拆诊断案例 | 2012款路虎揽胜运动版柴油车加速无力

故障现象  一辆2012款路虎揽胜运动版车&#xff0c;搭载3.0T柴油发动机&#xff08;型号为306DT&#xff09;&#xff0c;累计行驶里程约为10.2万km。车主进厂反映&#xff0c;车辆行驶中加速无力&#xff0c;且发动机故障灯异常点亮。 故障诊断 接车后试车&#xff0c;发动…

解决 npm xxx was blocked, reason: xx bad guy, steal env and delete files

问题复现 今天一位朋友说&#xff0c;vue2的老项目安装不老依赖&#xff0c;报错内容如下&#xff1a; npm install 451 Unavailable For Legal Reasons - GET https://registry.npmmirror.com/vab-count - [UNAVAILABLE_FOR_LEGAL_REASONS] vab-count was blocked, reas…

cudatoolkit安装(nvcc -V错误版本解决)

CudaToolKit安装&#xff08;nvcc&#xff09; cudatoolkit 是 CUDA 开发工具包&#xff08;CUDA Toolkit&#xff09; 的核心部分&#xff0c;包含了一系列用于开发和运行 CUDA 应用程序的软件组件。nvcc 是 NVIDIA CUDA 编译器驱动&#xff0c;用于将 CUDA C/C 代码编译成可…

数据新时代:如何选择现代数据治理平台(上)

谈现代数据治理系统的十大架构特征 最近一位老友找到我&#xff0c;咨询他的数据治理平台到底该不该换&#xff0c;背景是这样的&#xff1a;若干年前采购了一个市场主流的数据治理平台&#xff0c;功能大概就是数据治理三件套——标准、元数据和质量等经典数据治理的功能。现…

基于AXI PCIE IP的FPGA PCIE卡示意图

创作不易&#xff0c;转载请注明出处&#xff1a;https://blog.csdn.net/csdn_gddf102384398/article/details/143926217 上图中&#xff0c;在FPGA PCIE卡示意图内&#xff0c;有2个AXI Master设备&#xff0c;即&#xff1a;PCIE到AXI4-Full-Master桥、AXI CDMA IP&#xff1…

案例研究|阿特斯的JumpServer分布式部署和多组织管理实践

苏州阿特斯阳光电力科技有限公司&#xff08;以下简称为阿特斯&#xff09;是一家集太阳能光伏组件制造和为全球客户提供太阳能应用产品研发、设计、制造、销售的专业公司。 阿特斯集团总部位于加拿大&#xff0c;中国区总部位于江苏省苏州市。通过全球战略和多元化的市场布局…