题目 B: 货币套利 时间限制:1Sec 内存限制:64MB 提交:36 解决:4 [提交] [状态] 题目描述 套利是利用多国之间货币兑换率的差异，把某国单位币值经多种货币兑换后实现升值的牟利方式。例如，假设 1 美元能兑 0.5 英镑，1 英镑能兑换 10.0 法郎，1 法郎能兑换 0.21 美元，那么，通过货币转换，聪明的商人可以使得 1 美元经兑换变成 1*0.5*10.0*0.21＝1.05 美元，获利 5%。 你的工作是编写一个程序，以货币兑换率的列表作为输入，然后确定是否可能套利。 输入 多组测试数据。每组数据： 第一行一个整数 n（1≤n≤30，n=0 时表示输入结束），表示不同货币的数量。 接下来 n 行，每行一个字符串，表示一种货币的名称。字符串仅由大小写字母组成，长度不超过 30 个字符。 接下来一行一个整数 m，表示有 m 对货币兑换率。 最后 m 行，每行三项数据，分别为一个字符串 ci，一个实数 rij（0<rij<1000，3 位小数），一个字符串 cj。表示货币 ci 兑换货币 cj 的兑换率为 rij --- 即 1 单位 ci 能兑换成 rij 单位 cj。该货币兑换是单向的，即 "ci rij cj" 不能说明 cj 可以按 rij 或 1/rij 兑换为 ci。这里没有列出兑换率的两种货币是无法直接相互兑换的。 两组数据之间由一个空行分隔。 输出 每组数据输出一行，格式参考样例输出结果。如果可以套利，结果中包含 "Yes"，否则包含 "No"。

这道题目是关于货币套利的问题。给定一组货币兑换率的列表，要求判断是否存在套利的可能。

我会编写一个程序来解决这个问题。首先，我们需要读取输入数据。每组数据的格式如下：
- 第一行是一个整数n，表示不同货币的数量。
- 接下来的n行，每行是一个字符串，表示一种货币的名称。
- 接下来一行是一个整数m，表示有m对货币兑换率。
- 最后m行，每行包含三项数据：一个字符串ci，一个实数rij（表示货币ci兑换为cj的兑换率），一个字符串cj。

接下来，我们需要判断是否存在套利的可能。我们可以使用图论中的负权环检测算法来解决这个问题。具体步骤如下：
1. 创建一个图，将货币名称作为图的节点。
2. 根据兑换率创建图的边，如果货币ci可以兑换为cj，则在ci和cj之间创建一条边，边的权重为-log(rij)。
3. 对图中的每个节点进行松弛操作（Bellman-Ford算法），重复n-1次。
4. 如果在第n次松弛操作后，仍然存在可以松弛的节点，则存在负权环，即存在套利的可能。

最后，根据检测结果输出"Yes"或"No"。

下面是一个示例的实现代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <limits>

using namespace std;

struct Edge {
    int source;
    int target;
    double weight;
};

bool arbitrage(int n, vector<string>& currencies, vector<Edge>& edges) {
    vector<double> distance(n, numeric_limits<double>::max());
    distance[0] = 0;

    for (int i = 0; i < n - 1; i++) {
        for (const auto& edge : edges) {
            double newDistance = distance[edge.source] - log(edge.weight);
            if (newDistance < distance[edge.target]) {
                distance[edge.target] = newDistance;
            }
        }
    }

    for (const auto& edge : edges) {
        if (distance[edge.source] - log(edge.weight) < distance[edge.target]) {
            return true;
        }
    }

    return false;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        vector<string> currencies(n);
        for (int i = 0; i < n; i++) {
            cin >> currencies[i];
        }

        int m;
        cin >> m;

        vector<Edge> edges;
        for (int i = 0; i < m; i++) {
            string ci, cj;
            double rij;
            cin >> ci >> rij >> cj;

            int source = find(currencies.begin(), currencies.end(), ci) - currencies.begin();
            int target = find(currencies.begin(), currencies.end(), cj) - currencies.begin();

            edges.push_back({source, target, rij});
        }

        bool result = arbitrage(n, currencies, edges);
        cout << (result ? "Yes" : "No") << endl;
    }

    return 0;
}

希望能够帮助到你！如果有任何疑问，请随时提问。