POJ 2240 Arbitrage：貨幣套利與 Bellman-Ford 正環檢測詳解

題目大意

給定 n 種貨幣與 m 條兌換規則（有向邊），每條規則為 u v rate 表示 1 單位貨幣 u 可兌換 rate 單位貨幣 v。判斷是否存在**套利機會**：即從某貨幣出發，經一系列兌換後回到原貨幣，最終持有量 **> 1**。多組測資，n=0 結束。

模型轉換：乘法轉加法、尋找正環

令邊權重 w = log(rate)，則路徑乘積對應權重**和**。套利條件 rate1 * rate2 * ... > 1 ⇔ log(rate1) + log(rate2) + ... > 0。因此問題轉化為：**圖中是否存在總權重為正的環（正環）**。

Bellman-Ford 算法標準用於檢測**負環**（最短路徑）。若將權重取負 w' = -log(rate)，則套利 ⇔ 存在**負環**。也可直接修改鬆弛條件檢測正環：

if (dis[v] < dis[u] * rate) dis[v] = dis[u] * rate; // 乘法版鬆弛

完整 AC 代碼（C++，含精度處理）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50, MAXM = 1010;

struct Edge { int u, v; double w; } edges[MAXM];
double dis[MAXN];
char name[MAXN][MAXN];
int n, m, edgeCnt, caseNo;

bool bellmanFord(int start) {
    fill(dis, dis + n, 0.0);
    dis[start] = 1.0;                     // 關鍵：起點初始為 1
    for (int i = 0; i < n; ++i) {         // n 輪鬆弛
        bool updated = false;
        for (int j = 0; j < edgeCnt; ++j) {
            if (dis[edges[j].v] < dis[edges[j].u] * edges[j].w) {
                dis[edges[j].v] = dis[edges[j].u] * edges[j].w;
                updated = true;
            }
        }
        if (!updated) break;              // 提前收斂
    }
    // 第 n+1 輪若仍能鬆弛 → 存在正環
    for (int j = 0; j < edgeCnt; ++j)
        if (dis[edges[j].v] < dis[edges[j].u] * edges[j].w)
            return true;
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    while (cin >> n, n) {
        for (int i = 0; i < n; ++i) cin >> name[i];
        cin >> m;
        edgeCnt = 0;
        for (int i = 0; i < m; ++i) {
            char a[MAXN], b[MAXN]; double r;
            cin >> a >> r >> b;
            int u = find(name, name + n, a) - name;
            int v = find(name, name + n, b) - name;
            edges[edgeCnt++] = {u, v, r};
        }
        bool arbitrage = false;
        for (int i = 0; i < n && !arbitrage; ++i) // 枚舉起點
            arbitrage = bellmanFord(i);
        cout << "Case " << ++caseNo << ": " << (arbitrage ? "Yes" : "No") << '\n';
    }
    return 0;
}

關鍵細節與避坑指南

1. 起點初始化 dis[start] = 1.0：原代碼漏寫導致全 0，永遠無法鬆弛。
2. 枚舉所有起點：圖可能不連通，必須從每個節點嘗試。
3. 精度問題：連乘極易下溢/上溢。實際比賽中常改用 log 轉加法，或用 long double。本題資料範圍允許 double 直接乘法通過。
4. 邊數上限：m ≤ 1000，n ≤ 30，複雜度 O(n * m) 極快。

複雜度分析

• 時間：O(n²m)（最壞枚舉 n 起點 × n 輪 × m 邊），實際 < 10⁶ 操作
• 空間：O(n + m)

延伸：SPFA 優化

使用隊列優化 Bellman-Ford（SPFA），僅將鬆弛成功的節點入隊，平均接近 O(m)，但最壞仍為 O(nm)。對本題規模基本不必要，但模板值得掌握。