题解

涉及知识点

1. 图论与最短路径

   • 将货币视为图的节点，汇率 $r_{ij}$ 视为从 $c_i$ 到 $c_j$ 的边权。
   • 套利问题转化为 图中是否存在正权环（即通过货币循环兑换后利润 $>1$）。

2. Bellman-Ford 算法

   • 用于检测图中是否存在从某节点出发经过循环后权重乘积 $>1$ 的路径。

3. 对数转换

   • 将汇率乘积问题转化为对数求和问题（避免浮点数溢出）：
     [ \log(r_1 \times r_2 \times \dots \times r_k) = \log r_1 + \log r_2 + \dots + \log r_k ]
     若和为正值，则原乘积 $>1$。

解法代码（C++）

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <cmath>
using namespace std;

const double INF = 1e9;

bool hasArbitrage(int n, const vector<vector<double>>& adj) {
    vector<double> dist(n, 0.0);
    dist[0] = 1.0;  // 假设从第0种货币开始

    // Relax all edges n-1 times
    for (int i = 0; i < n - 1; ++i) {
        for (int u = 0; u < n; ++u) {
            for (int v = 0; v < n; ++v) {
                if (dist[u] * adj[u][v] > dist[v]) {
                    dist[v] = dist[u] * adj[u][v];
                }
            }
        }
    }

    // Check for positive cycles
    for (int u = 0; u < n; ++u) {
        for (int v = 0; v < n; ++v) {
            if (dist[u] * adj[u][v] > dist[v] + 1e-8) {  // 避免浮点误差
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n, caseNum = 1;
    while (cin >> n, n != 0) {
        map<string, int> currencyIndex;
        for (int i = 0; i < n; ++i) {
            string name;
            cin >> name;
            currencyIndex[name] = i;
        }

        vector<vector<double>> adj(n, vector<double>(n, 0.0));
        int m;
        cin >> m;
        while (m--) {
            string from, to;
            double rate;
            cin >> from >> rate >> to;
            int u = currencyIndex[from], v = currencyIndex[to];
            adj[u][v] = rate;
        }

        if (hasArbitrage(n, adj)) {
            cout << "Case " << caseNum++ << ": Yes" << endl;
        } else {
            cout << "Case " << caseNum++ << ": No" << endl;
        }
    }
    return 0;
}

代码解释

1. 输入处理：

   • 使用 map 存储货币名称到索引的映射。
   • 构建邻接矩阵 adj，其中 adj[u][v] 表示货币 $u$ 到 $v$ 的汇率。

2. Bellman-Ford 算法：

   • 初始化距离数组 dist，表示从起点货币出发的当前最大兑换值。
   • 松弛所有边 $n-1$ 次，更新 dist[v]。
   • 检查是否存在正权环（即是否可以通过循环兑换增加利润）。

3. 输出结果：

   • 根据检测结果输出 Yes 或 No。

复杂度分析

• 时间复杂度：$O(n^3)$（Bellman-Ford 算法的三重循环）。
• 空间复杂度：$O(n^2)$（存储邻接矩阵）。

总结

本题通过 图的建模 和 Bellman-Ford 算法，高效检测货币兑换环路中是否存在套利机会。关键在于将汇率乘积问题转化为图论中的正权环检测问题。