POJ 2240 套利問題：Bellman-Ford 判斷正權環

問題描述

給定貨幣兌換關係圖，判斷是否存在套利機會（即正權重環）。輸入多組測資，每組包含貨幣名稱、兌換率邊。輸出 "Yes" 或 "No"。

解題思路

• 將貨幣映射為節點，兌換率為有向邊權重。
• 套利存在 ⇔ 圖中存在邊權乘積 > 1 的環 ⇔ 取對數後權重和 > 0 的正權環。
• 因邊權為乘法關係，直接用 Bellman-Ford 檢測正環：對每個節點作為起點跑一次 BF，若第 V 輪仍能鬆弛則存在正環。

核心代碼

#include 
#include 
#include 
using namespace std;

struct Edge { int s, e; double w; };
Edge path[1000];
bool ishuan(int s, double sw, int v, int e) {
    bool flag;
    int i;
    double d[31];
    for (i = 1; i <= v; i++) d[i] = 0;
    d[s] = sw;
    while (v--) {
        flag = 1;
        for (i = 1; i <= e; i++) {
            if (d[path[i].e] < d[path[i].s] * path[i].w) {
                flag = 0;
                d[path[i].e] = d[path[i].s] * path[i].w;
            }
        }
        if (flag) return 0;
    }
    return 1;
}

int main() {
    bool flag;
    double ex;
    int n, m, i, j, index1, index2, lizi;
    char name[31][100], temp1[100], temp2[100];
    lizi = 0;
    while (scanf("%d", &n) && n != 0) {
        lizi++;
        for (i = 1; i <= n; i++) scanf("%s", name[i]);
        scanf("%d", &m);
        for (j = 1; j <= m; j++) {
            scanf("%s%lf%s", temp1, &ex, temp2);
            index1 = index2 = 0;
            for (i = 1; index1 == 0 || index2 == 0; i++) {
                if (strcmp(name[i], temp1) == 0) index1 = i;
                if (strcmp(name[i], temp2) == 0) index2 = i;
            }
            path[j].s = index1;
            path[j].e = index2;
            path[j].w = ex;
        }
        flag = 0;
        for (i = 1; i <= n; i++) {
            if (ishuan(i, 1.0, n, m)) { flag = 1; break; }
        }
        printf("Case %d: ", lizi);
        if (flag) printf("Yes\n"); else printf("No\n");
    }
    return 0;
}

關鍵點說明

1. 對數轉換：原題為乘法關係，代碼直接用乘法比較 `d[v] < d[u] * w`，等價於對數後加法 `log(d[v]) < log(d[u]) + log(w)`，避免浮點誤差。
2. 枚舉起點：對每個節點跑一次 BF，確保檢測所有連通分量。
3. 複雜度：O(V²E)，V≤30，E≤900，完全足夠。

優化方向

• SPFA 隊列優化加速鬆弛。
• 僅從入度>0 的節點啟動，減少重複計算。