网站图片优化工具,起域名网站,潍坊市建设监理协会网站,田园综合体建设网站E : 货币套汇#xff08;图路径#xff09;
Description
套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如#xff0c;假定1 美元可以买0.7 英镑#xff0c;1 英镑可以买9.5 法郎#xff0c;1法郎可以买到0.16美元。通过货币兑换图路径
Description
套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如假定1 美元可以买0.7 英镑1 英镑可以买9.5 法郎1法郎可以买到0.16美元。通过货币兑换一个商人可以从1 美元开始买入得到0.7×9.5×0.161.064美元从而获得6.4%的利润。 给定n种货币c1 ,c2 ,… ,cn的有关兑换率试设计一个有效算法确定货币间是否存在套汇的可能性。
提示判断图上是否出现正环,即环上所有的边相乘大于1
Input
第一行测试数据组数 每组测试数据格式为 第一行正整数n (1 n 30)正整数m分别表示n种货币和m种不同的货币兑换率。 2~n1行n种货币的名称。 n2~nm1行每行有3 个数据项cirij 和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 USDollarOutput
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; // 自环设置为1elsedist[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;
}
