【数据结构】E : 货币套汇（图路径）

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;
}