POJ 2240 Arbitrage：貨幣套利檢測（Floyd / Bellman-Ford 判正環）

問題描述

給定 n (≤30) 種貨幣及 m 條匯率邊（有向，權重為匯率）。判斷是否存在一條循環路徑，使得起始貨幣經過兌換後數量增值（即路徑上匯率乘積 > 1）。多組測資，n=0 結束。

核心模型

構建有向圖，邊權為匯率 r_ij。尋找是否存在環使得 ∏ r > 1。
取對數轉化為加法：log(∏ r) = ∑ log(r)。若存在 ∑ log(r) > 0 的環，即為正權環。
但直接用乘法更直觀：求最大乘積路徑，若對角線 maxProd[i][i] > 1 則存在套利。

解法一：Floyd 最大乘積路徑

初始化 mp[i][j] = 0，mp[i][i] = 1。讀入邊賦值。
三重循環：

for k=0..n-1
  for i=0..n-1
    for j=0..n-1
      if (mp[i][j] < mp[i][k] * mp[k][j])
          mp[i][j] = mp[i][k] * mp[k][j];

最後檢查 mp[i][i] > 1 是否存在。

解法二：Bellman-Ford 判正環（SPFA 變體）

將乘法轉化為加法：對數後求最長路，但直接用乘法也可。
初始 dist[0] = 1，其餘 0。對所有邊鬆弛 n 輪：

if (dist[v] < dist[u] * rate) dist[v] = dist[u] * rate;

第 n 輪若仍能鬆弛，說明存在正環（套利）。

參考代碼（Floyd 版）

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, caseNo = 0;
    while (cin >> n, n) {
        vector name(n);
        for (int i = 0; i < n; ++i) cin >> name[i];
        unordered_map id;
        for (int i = 0; i < n; ++i) id[name[i]] = i;

        vector> mp(n, vector(n, 0));
        for (int i = 0; i < n; ++i) mp[i][i] = 1;

        int m; cin >> m;
        for (int i = 0; i < m; ++i) {
            string c1, c2; double r;
            cin >> c1 >> r >> c2;
            mp[id[c1]][id[c2]] = r;
        }

        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    if (mp[i][j] < mp[i][k] * mp[k][j])
                        mp[i][j] = mp[i][k] * mp[k][j];

        bool ok = false;
        for (int i = 0; i < n; ++i) if (mp[i][i] > 1) { ok = true; break; }

        cout << "Case " << ++caseNo << ": " << (ok ? "Yes" : "No") << '\n';
    }
    return 0;
}

關鍵細節

• 貨幣名稱無空格，可直接 cin >> string 讀取。
• 測資之間有空行，cin 自動跳過空白字符，無需額外處理。
• Floyd 複雜度 O(n^3) = 27000，極快；Bellman-Ford O(n*m) 同樣快。
• 雙精度浮點數精度足夠，無需對數轉換避免精度損失。

樣例驗證

Input:
3
USDollar BritishPound FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3
USDollar BritishPound FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar
0

Output:
Case 1: Yes
Case 2: No

總結

POJ 2240 是「判斷圖中是否存在正權環」的經典應用。Floyd 最大乘積路徑代碼最短、邏輯最清晰；Bellman-Ford 適用於稀疏圖或需重構為加法模型時。掌握「匯率乘積 > 1 ⇔ 套利」建模即可舉一反三解決類似問題。