货币兑换问题
一 原问题链接
[Currency Exchange - POJ 1860 - Virtual Judge
Coin Exchange Problem (POJ 1860) on Virtual Judge
二 输入和输出
1 输入
输入的第一行为4个数字：N代表货币类型的数量,M代表交换点的数量,S代表货币类型,V代表货币数量.接着是M行数据:每个后续的行都包含六个数字来描述相应的交换点情况.这些数字由一个或多个空格分隔开.
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次迭代后（其中n代表图中顶点的数量），再执行一次验证操作即可判断是否存在环。需要注意的是，在处理双向边时（即两条方向相反但权值相同的边），总边数为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;
}
代码解释七 测试
