E : 货币套汇(图路径)
Description
套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如,假定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
Input
第一行:测试数据组数
每组测试数据格式为:
第一行:正整数n (1< =n< =30),正整数m,分别表示n种货币和m种不同的货币兑换率。
2~n+1行,n种货币的名称。
n+2~n+m+1行,每行有3 个数据项ci,rij 和cj ,表示货币ci 和cj的兑换率为 rij。
Output
对每组测试数据,如果存在套汇的可能则输出YES
如果不存在套汇的可能,则输出NO。
Sample
Input
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
Output
YES
NO
解题思路
这一道题就是在一个加权有向图中检测是否存在正权重环,这里的关键是如何利用图论和弗洛伊德算法来解决这个问题。为什么能够使用Folyd算法呢?这就要考虑到Folyd算法的作用,**弗洛伊德算法能够计算图中所有顶点对之间的最短路径。在这个问题中,我们将算法用于计算“最优”兑换路径,即使得货币数量最大化的路径。**所以同样是求最优的,用于正权重环同样可以适用。这一道题的注意点就是:**不能互相兑换的货币的处理和自环的预处理。
AC代码
#include <iostream>
#include <string>
using namespace std;
const double EPS = 1e-7; // 表示非常小的数,用于初始化没有直接兑换率的情况
int n, m;
int getIndex(string arr, string message[]) {
for (int i = 0; i < n; i++)
if (message[i] == arr)
return i;
}
void Folyd(double** data) {
double** dist = new double* [n];
for (int i = 0; i < n; i++) {
dist[i] = new double[n];
for (int j = 0; j < n; j++) {
if (i == j)
dist[i][j] = 1.0; // 自环设置为1
else
dist[i][j] = data[i][j] > EPS ? data[i][j] : EPS;
}
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (dist[i][j] < dist[i][k] * dist[k][j])
dist[i][j] = dist[i][k] * dist[k][j];
for (int i = 0; i < n; i++) {
if (dist[i][i] > 1.0) {
cout << "YES" << endl;
// 释放内存
for (int i = 0; i < n; i++) {
delete[] dist[i];
}
delete[] dist;
return;
}
}
cout << "NO" << endl;
// 释放内存
for (int i = 0; i < n; i++) {
delete[] dist[i];
}
delete[] dist;
}
int main() {
string message[40];
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> message[i];
double** data = new double* [n];
for (int i = 0; i < n; i++) {
data[i] = new double[n];
for (int j = 0; j < n; j++)
data[i][j] = (i == j) ? 1.0 : EPS;
}
for (int i = 0; i < m; i++) {
string a, c;
double b;
cin >> a >> b >> c;
data[getIndex(a, message)][getIndex(c, message)] = b;
}
Folyd(data);
// 释放内存
for (int i = 0; i < n; i++) {
delete[] data[i];
}
delete[] data;
}
return 0;
}
原文地址:https://blog.csdn.net/likinguuu/article/details/134586744
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_2113.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!