您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

POJ 1860 Currency Exchange:用 Bellman-Ford 偵測正權迴圈

編輯:iOS 開發綜合

題目在問什麼

給你 n 種貨幣、m 組兌換關係。每組關係包含兩個方向的匯率與手續費。規則是:把 A 換成 B 時,先扣手續費,再乘上匯率。問:從某種起始貨幣出發,能否透過一連串兌換讓自己的錢變多?

為什麼是正環問題

把每筆兌換看成圖上的一條加權邊,狀態轉移就是:

dist[v] = (dist[u] - commission) * rate

只要存在一個迴圈,繞一圈之後金額反而變大,那麼就可以無限次繞下去,財富沒有上限。這種迴圈就是所謂的「正環」,等價於最短路徑問題中的負環,只是權重方向相反。

偵測方式沿用 Bellman-Ford 的標準套路:先做 n-1 輪鬆弛,再檢查第 n 輪是否還能繼續鬆弛。若還能,代表存在可無限改善的迴圈。

程式碼

#include <string.h>
#include <stdio.h>

const int N = 110;
const int inf = 0x3fffffff;

int start, num, n;
double dist[N], wf;

struct edge {
    int st, ed;
    double cost, w;
} e[220];

void addedge(int x, int y, double w, double c) {
    e[num].st = x;
    e[num].ed = y;
    e[num].cost = c;
    e[num++].w = w;
}

int Bellman_Ford() {
    int flag = 0, i, u, v, j;
    for (i = 1; i <= n; i++) dist[i] = 0;
    dist[start] = wf;

    for (i = 1; i < n; i++) {          // n-1 輪鬆弛
        for (j = 0; j < num; j++) {
            u = e[j].st;
            v = e[j].ed;
            if (dist[v] < (dist[u] - e[j].cost) * e[j].w) {
                dist[v] = (dist[u] - e[j].cost) * e[j].w;
                flag = 1;
            }
        }
        if (flag == 0) break;          // 本輪無更新,提前結束
    }

    for (i = 0; i < num; i++)           // 第 n 輪仍可鬆弛,代表有正環
        if (dist[e[i].ed] < (dist[e[i].st] - e[i].cost) * e[i].w)
            return 1;
    return 0;
}

int main() {
    int m, i, x, y;
    double a, b, c, d;
    while (scanf("%d%d%d%lf", &n, &m, &start, &wf) != -1) {
        num = 0;
        for (i = 1; i <= m; i++) {
            scanf("%d%d%lf%lf%lf%lf", &x, &y, &a, &b, &c, &d);
            addedge(x, y, a, b);       // x 換到 y
            addedge(y, x, c, d);       // y 換到 x,方向相反、參數不同
        }
        if (Bellman_Ford()) printf("YES\n");
        else                printf("NO\n");
    }
    return 0;
}

幾個實作細節

  • 初始化把所有 dist 設為 0 而非負無限大,因為金額必為正,等價於只有起點可達。
  • 兩組兌換參數必須建成兩條有向邊,方向相反時匯率與手續費都不一樣,不能共用。
  • 這裡用 double 存金額,比較時直接寫 < 即可,精度在本题的規模下足夠。
  • 另一種常見寫法是對權重取負對數,把乘法問題轉成加法最短路,再用 SPFA 判負環,兩者複雜度同級。
  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved