首页 > 代码库 > poj 1860 Currency Exchange 解题报告

poj 1860 Currency Exchange 解题报告

2024-07-17 16:31:38   225人阅读

题目链接：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.csdn.net/lyhvoyage/article/details/19281013

       可以说，是用了Bellman_ford 的 逆向思维。传统的Bellman_ford 是用来求可以含有负边权的最短路径，且判断是否有负权回路。

       这个题目希望我们验证是否存在正权回路：顶点的权值能不断增加，且能无限一直松弛下去。

       不过初始化与传统的Bellman_ford 是不同的， dist[S] = V，其他dist[i] = 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[maxv];10 int cnt, type;11 int N, M;12 13 struct node14 {15     int a, b;16     double rate, commission;17 }currency[maxn];18 19 bool Bellman_ford()20 {21     for (int i = 1; i <= N; i++)22         dist[i] = (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[currency[j].a] - currency[j].commission) * currency[j].rate;29             if (t > dist[currency[j].b])30             {31                 dist[currency[j].b] = (dist[currency[j].a] - currency[j].commission) * currency[j].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[currency[j].a] - currency[j].commission) * currency[j].rate;41         if (t > dist[currency[j].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[cnt].a = A;58             currency[cnt].b = B;59             currency[cnt].rate = Rab;60             currency[cnt].commission = Cab;61 62             currency[++cnt].a = B;63             currency[cnt].b = A;64             currency[cnt].rate = Rba;65             currency[cnt++].commission = Cba;66         }67         printf("%s\n", Bellman_ford() ? "YES" : "NO");68     }69     return 0;70 }

 


联系
我们