您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

UVA 104 Arbitrage：Floyd-Warshall 最大乘積路徑與最短套利序列

編輯：關於C++

題目大意

n 種貨幣，給定匯率矩陣 rate[i][j] (i→j)。尋找一條循環路徑 (起終點相同)，使匯率乘積 > 1.01。若多解，要求邊數最少 (最短路徑)；再同長則字典序最小。輸出路徑節點序列 (1-based)。

核心思路：三維 DP + Floyd 變體

定義 dp[k][i][j] = 從 i 到 j 恰好經過 k 條邊 (即 k+1 個節點) 的最大匯率乘積。
遞推：dp[k][i][j] = max(dp[k][i][j], dp[k-1][i][m] * dp[1][m][j])。
路徑記錄：path[k][i][j] = m 表示中轉點。
檢查：對每 k，若 dp[k][i][i] > 1.01，找到長度為 k 的套利環。

完整程式碼 (C++)

#include 
using namespace std;

const int MAXN = 32;
double dp[MAXN][MAXN][MAXN];
int path[MAXN][MAXN][MAXN];

void printPath(int i, int j, int k) {
    if (k == 0) return;
    int m = path[k][i][j];
    printPath(i, m, k-1);
    cout << m+1 << ' ';
    printPath(m, j, 0); // k=1 直接印終點由上層處理
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    while (cin >> n) {
        // 初始化
        for (int i=0;i> dp[1][i][j]; path[1][i][j] = j; }
            }

        bool found = false;
        int bestK = -1, bestI = -1;

        for (int k=2; k<=n && !found; ++k) {
            for (int m=0; m 0)
                        for (int j=0; j 0) {
                                double val = dp[k-1][i][m] * dp[1][m][j];
                                if (val > dp[k][i][j]) {
                                    dp[k][i][j] = val;
                                    path[k][i][j] = m;
                                }
                            }
            for (int i=0; i 1.01) {
                    found = true; bestK = k; bestI = i; break;
                }
        }

        if (!found) {
            cout << "no arbitrage sequence exists\n";
        } else {
            cout << bestI+1 << ' ';
            // 遞迴印出中間節點
            function dfs = [&](int i, int j, int k) {
                if (k == 1) return;
                int m = path[k][i][j];
                dfs(i, m, k-1);
                cout << m+1 << ' ';
            };
            dfs(bestI, bestI, bestK);
            cout << bestI+1 << '\n';
        }
    }
    return 0;
}