HDU 1217 Arbitrage：弗洛伊德演算法檢測貨幣套利機會

題目大意

給定 N 種貨幣與 M 個匯率（有向邊權重），判斷是否存在一條兌換路徑，使得某貨幣經多次兌換後價值超過初始值（即匯率乘積 > 1）。

解題思路：最大路徑乘積

將貨幣視為圖的節點，匯率為邊權重。問題轉化為：圖中是否存在權重乘積大於 1 的環。
使用 Floyd-Warshall 演算法 求任意兩點間的最大乘積路徑。若任一 map[i][i] > 1，即存在套利機會。

演算法流程

1. 初始化鄰接矩陣 map[i][j] 為匯率（無連線為 0）。
2. 三層迴圈 k, i, j 松弛：if (map[i][k] * map[k][j] > map[i][j]) map[i][j] = map[i][k] * map[k][j];
3. 檢查對角線 map[i][i] > 1，若真輸出 "Yes"，否則 "No"。

關鍵代碼實現 (C++)

#include <iostream>
#include <cstring>
#include <map>
#include <string>
using namespace std;

const int MAXN = 40;
double rate[MAXN][MAXN];
string name[MAXN];
int n, m, caseNo = 1;

int getId(const string& s) {
    for (int i = 0; i < n; ++i) if (name[i] == s) return i;
    return -1;
}

int main() {
    while (cin >> n, n) {
        for (int i = 0; i < n; ++i) cin >> name[i];
        cin >> m;
        memset(rate, 0, sizeof(rate));
        for (int i = 0; i < m; ++i) {
            string s1, s2; double x;
            cin >> s1 >> x >> s2;
            rate[getId(s1)][getId(s2)] = x;
        }
        // Floyd 求最大乘積
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    if (rate[i][k] * rate[k][j] > rate[i][j])
                        rate[i][j] = rate[i][k] * rate[k][j];
        bool arbitrage = false;
        for (int i = 0; i < n; ++i) if (rate[i][i] > 1.0) { arbitrage = true; break; }
        cout << "Case " << caseNo++ << ": " << (arbitrage ? "Yes" : "No") << endl;
    }
    return 0;
}

複雜度與優化

• 時間複雜度：O(N^3)，N ≤ 30 完全足夠。
• 空間複雜度：O(N^2)。
• 提前剪枝：迴圈中若發現 rate[0][0] > 1 可直接跳出（原代碼做法）。

總結

本題是 Floyd 演算法的經典變體應用——將「加法最短路徑」轉為「乘法最大路徑」。掌握權重運算語意轉換，是解決此類圖論問題的關鍵。