POJ1860 Currency Exchange(最短路)

题目链接。

分析：

以前没做出来，今天看了一遍题竟然直接A了。出乎意料。

大意是这样，给定不同的金币的编号，以及他们之间的汇率、手续费，求有没有可能通过不断转换而盈利。

直接用Bellman-ford检测负环的方法检测。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 300;
const int inf = (1<<30);

struct Node {
    int u, v;
    double r, c;
    int next;
}node[maxn];

int n, m, s, cn, head[120];
double q, d[120];

void add_edge(int u, int v, double r, double c) {
    node[cn].u = u;
    node[cn].v = v;
    node[cn].r = r;
    node[cn].c = c;
    node[cn].next = head[u];
    head[u] = cn++;
}

bool bellman_ford(int s) {
    for(int i=0; i<n; i++) d[i] = -inf;
    d[s] = q;

    for(int i=0; i<n-1; i++) {
        for(int i=0; i<cn; i++) {
            Node &e = node[i];

            if(d[e.u] != -inf && (d[e.u]-e.c)*e.r>d[e.v]) {
                d[e.v] = (d[e.u]-e.c)*e.r;
            }
        }
    }


    for(int i=0; i<cn; i++) {
        Node &e = node[i];

        if(d[e.u] != -inf && (d[e.u]-e.c)*e.r>d[e.v]) {
            return true;
        }
    }
    return false;
}

int main() {
    int u, v;
    double r1, c1, r2, c2;

    while(scanf("%d %d %d %lf", &n, &m, &s, &q) == 4) {
        cn = 0;

        memset(head, -1, sizeof(head));

        for(int i=0; i<m; i++) {
            scanf("%d %d %lf %lf %lf %lf", &u, &v, &r1, &c1, &r2, &c2);
            u--; v--;
            add_edge(u, v, r1, c1);
            add_edge(v, u, r2, c2);
        }

        if(bellman_ford(s-1)) printf("YES
");
        else printf("NO
");
    }


    return 0;
}