一 原问题链接

Currency Exchange - POJ 1860 - Virtual Judge

https://vjudge.net/problem/POJ-1860

二 输入和输出

1 输入

输入的第1行包含 4 个数字：N 表示货币类型的数量，M 表示交换点的数量，S 表示货币类型，V 表示货币数量。然后是 M 行，每行都包含 6 个数字，表示相应交换点的描述。数字由一个或多个空格隔开。

2 输出

如果可以增加财富，则输出“YES”，在其他情况下输出“NO”

三 输入和输出样例

1 输入样例

3 2 1 20.0

1 2 1.00 1.00 1.00 1.00

2 3 1.10 1.00 1.10 1.00

2 输出样例

YES

四 分析

从当前货币出发，走一个回路，赚到一些钱。因为走过的边是双向的，因此能走过去就一定能够走回来。只需要判断图中是否有正环，即使这个正环不包含 S 也没关系，走一次正环就能赚一些钱。

样例1，如下图所示，包含一个正环 2-3-2，每走一次就赚一些钱。

计算过程如下：
1-2:(20-1.00)*1.00=19.00

2-3 3-2:(19-1.00)*1.1.=19.80 (19.80-1.00)*1.10=20.68

2-3 3-2:(20.68-1.00)*1.10=21.648 (21.648-1.00)*1.1.=22.7128

2-1:(22.7128-1.00)*1.00=21.7128

五 算法设计

可采用 Bellman-Ford 算法，判断正环。用边松弛 n-1 次后，再执行一次，如果还可以松弛，则说明有环（是正环还是负环，主要取决于松弛条件）。注意：对双向边，边数是 2m 或使用边数计数器 cnt。

六 实现

package graph.poj1860;

import java.util.Scanner;

public class Poj1860 {
    static node e[] = new node[210];
    static int n;
    static int m;
    static int s;
    static int cnt = 0;
    static double v;

    static double dis[] = new double[110];

    static {
        for (int i = 0; i < e.length; i++) {
            e[i] = new node();
        }
    }

    static void add(int a, int b, double r, double c) {
        e[cnt].a = a;
        e[cnt].b = b;
        e[cnt].r = r;
        e[cnt++].c = c;
    }

    static boolean bellman_ford() { // 判正环
        for (int i = 0; i < dis.length; i++) {
            dis[i] = 0;
        }
        dis[s] = v;
        for (int i = 1; i < n; i++) { // 执行 n-1次
            boolean flag = false;
            for (int j = 0; j < cnt; j++) // 注意：边数是 2m 或使用 cnt
                if (dis[e[j].b] < (dis[e[j].a] - e[j].c) * e[j].r) {
                    dis[e[j].b] = (dis[e[j].a] - e[j].c) * e[j].r;
                    flag = true;
                }
            if (!flag)
                return false;
        }
        for (int j = 0; j < cnt; j++) // 再执行1次，还能松弛说明有环
            if (dis[e[j].b] < (dis[e[j].a] - e[j].c) * e[j].r)
                return true;
        return false;
    }

    public static void main(String[] args) {
        int a, b;
        double rab, cab, rba, cba;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        s = scanner.nextInt();
        v = scanner.nextDouble();
        for (int i = 0; i < m; i++) {
            a = scanner.nextInt();
            b = scanner.nextInt();
            rab = scanner.nextDouble();
            cab = scanner.nextDouble();
            rba = scanner.nextDouble();
            cba = scanner.nextDouble();
            add(a, b, rab, cab);
            add(b, a, rba, cba);
        }
        if (bellman_ford())
            System.out.println("YES");
        else
            System.out.println("NO");
    }
}

class node {
    int a;
    int b;
    double r;
    double c;
}

七 测试