poj 1860 Currency Exchange 解题报告
题目链接：http://poj.org/problem?id=1860题目意思：给出 N 种 currency， M种兑换方式，Nick 拥有的的currency 编号S 以及他的具体的currency（V）。M 种兑换方式中每种用6个数描述: A, B, Rab, Cab, Rba, Cba。其中，Rab: 货币A 兑换 货币B 的汇率为Rab，佣金为Cab。Rba：货币B 兑换 货币 A 的汇率，佣金为Cba。假设含有的A货币是x，那么如果兑换成B，得到的货币B 就是：(x-Cab) * Rab。问从 货币S 经过一定次数的兑换，最终回归到货币S，能否使得 Nick 本来含有的 S 大。
思路我是借鉴这个人的：
http://blog.iyunv.com/lyhvoyage/article/details/19281013
可以说，是用了Bellman_ford 的 逆向思维。传统的Bellman_ford 是用来求可以含有负边权的最短路径，且判断是否有负权回路。
这个题目希望我们验证是否存在正权回路：顶点的权值能不断增加，且能无限一直松弛下去。
不过初始化与传统的Bellman_ford 是不同的， dist = V，其他dist = 0 / 无穷小。当 S 到其他点的 距离能不断增大时，说明存在正权回路。
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 using namespace std;
5
6 const int maxn = 1e4 + 10;
7 const int maxv = 100 + 5;
8
9 double has, dist;
10 int cnt, type;
11 int N, M;
12
13 struct node
14 {
15 int a, b;
16 double rate, commission;
17 }currency;
18
19 bool Bellman_ford()
20 {
21 for (int i = 1; i <= N; i++)
22 dist = (i == type ? has : 0);
23 for (int i = 1; i < N; i++)
24 {
25 bool flag = false;
26 for (int j = 1; j < cnt; j++)
27 {
28 double t = (dist.a] - currency.commission) * currency.rate;
29 if (t > dist.b])
30 {
31 dist.b] = (dist.a] - currency.commission) * currency.rate;
32 flag = true;
33 }
34 }
35 if (!flag)
36 break;
37 }
38 for (int j = 1; j < cnt; j++)
39 {
40 double t = (dist.a] - currency.commission) * currency.rate;
41 if (t > dist.b])
42 return true;
43 }
44 return false;
45 }
46
47 int main()
48 {
49 while (scanf("%d%d%d%lf", &N, &M, &type, &has) != EOF)
50 {
51 int A, B;
52 double Rab, Cab, Rba, Cba;
53 cnt = 1;
54 while (M--)
55 {
56 scanf("%d%d%lf%lf%lf%lf", &A, &B, &Rab, &Cab, &Rba, &Cba);
57 currency.a = A;
58 currency.b = B;
59 currency.rate = Rab;
60 currency.commission = Cab;
61
62 currency[++cnt].a = B;
63 currency.b = A;
64 currency.rate = Rba;
65 currency.commission = Cba;
66 }
67 printf("%s\n", Bellman_ford() ? "YES" : "NO");
68 }
69 return 0;
70 }
页:
[1]