【最短路-判断正权环 Bellman-Ford/Floyd】Arbitrage POJ - 2240

Arbitrage POJ - 2240

题意：

给出一系列货币汇率，问其中有无某种货币能在某些兑换操作后兑换回原货币，并且数量比开始时增多。

思路：

将货币视为节点，将兑换操作视为从一个节点到另一个节点的一条单向边。假定起点是1元，进行类似最短路的松弛操作后，再看起点是否多于1元即可。也就是判断是否存在正权环。

Bellman-Ford

const int maxn = 40;

int num = 0;
map<string, int> currency
struct Edge {
    int from, to;
    double dist;
};
vector<Edge> edges;
double d[maxn];
int n, m;

void init(int n) {
    num = 0;
    edges.clear();
    currency.clear();
    memset(d, 0, sizeof(d));
}

bool solve(int s) {
    memset(d, 0, sizeof(d));
    d[s] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < edges.size(); j++) {
            Edge& e = edges[j];
            if (d[e.from] * e.dist > d[e.to]) {
                d[e.to] = d[e.from] * e.dist;
            }
        }
    }
    if (d[s] > 1.0) return true;
    return false;
}

int main()
{
   // ios::sync_with_stdio(false);
   /// int t; cin >> t; while (t--) {
    int kase = 0;
    while (cin >> n && n) {
        init(n);
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            currency[s] = i;
        }
        cin >> m;

        for (int i = 1; i <= m; i++) {
            string u, v;
            double dis;
            cin >> u >> dis >> v;
            Edge t;
            t.from = currency[u];
            t.to = currency[v];
            t.dist = dis;
            edges.push_back(t);
        }

        int ok = 0;

        for (int i = 1; i <= n; i++) {
            if (solve(i)) {
                ok = 1;
                break;
            }
        }
        cout << "Case " << ++kase << ": ";
        if (!ok) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
   // }
    return 0;
}

Floyd

int n, m;
map<string, int> currency;
double edges[maxn][maxn];
double d[maxn];
double temp[maxn];

bool floyd() {
    for (int i = 1; i <= n; i++) {
        temp[i] = d[i];
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (d[i] * edges[i][j] > d[j]) {
                    d[j] = d[i] * edges[i][j];
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        if (d[i] > temp[i]) return true;
    }
    return false;
}

int main()
{
    // ios::sync_with_stdio(false);
    /// int t; cin >> t; while (t--) {
    int kase = 0;
    while (cin >> n && n) {
        memset(edges, INF, sizeof(edges));
        for (int i = 1; i <= n; i++) d[i] = 1;
        for (int i = 1; i <= n; i++) {
            string s;
            cin >> s;
            currency[s] = i;
        }
        cin >> m;
        for (int i = 1; i <= m; i++) {
            string u, v;
            double dis;
            cin >> u >> dis >> v;
            edges[currency[u]][currency[v]] = dis;
        }
        floyd();
        cout << "Case " << ++kase << ": ";
        if (floyd()) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}

【最短路-判断正权环 Bellman-Ford/Floyd】Arbitrage POJ - 2240

原文：https://www.cnblogs.com/streamazure/p/13405091.html