給你 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 存金額,比較時直接寫 < 即可,精度在本题的規模下足夠。