您的位置: 首页  >  IT文章  >  HDOJ-1217-Arbitrage 解题报告

HDOJ-1217-Arbitrage 解题报告

分类: IT文章 • 2022-06-04 09:23:47

<知识分享>

求最短路的题，与普通最短路不同的地方是运算是用乘法而不是加法。题意：套汇是指利用不同外汇市场的外汇差价，在某一外汇市场上买进某种货币，同时在另一外汇市场上卖出该种货币，以赚取利润。这种利润称之为套利。比如1美元可以买0.5英镑，而1英镑可以买10法郎，2法郎可以买1美元，那么可用通过套汇使用1美元买到2.5美元，套利是存在的。下面给出各个货币的种类和名称，再给出一些货币转换的汇率，请问是否存在套利？

       解题思路：因为汇率的转换是使用乘法，而与小于1的数相乘是会导致原来的数变小的，所以此题相当于是有负权的题目，很明显Dijkstra算法是不能使用的了。题目问套利是否存在，因此每种货币是否存在套利都应该考虑，货币种类不超过30，使用Floyd算法的耗时不会太多。再想想，题目中不一定给出的任意两种货币都能够互相转换，那么不能够转换的话我们如何表示它们之间的汇率呢？用0表示，这样则说明不能够转换。使用Floyd算法求每两种货币能够互相转换的最大汇率，那么最后我们判断每种货币转换为自己时的汇率是否大于1，是的话说明存在套利，否的话则说明本货币不存在套利。注意本题是单向图。

       接下来是解题代码：Floyd解法
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <string.h>  
  4. #define N 31  
  5. #define Max(a, b) (a > b ? a : b)  
  6.   
  7. int n, m;  
  8. double map[N][N];   //存储汇率  
  9. char str[N][N];     //存储货币名称  
  10.   
  11. void Init();  
  12.   
  13. void Read();  
  14.   
  15. int Count(char s[]);   //计算字符串编号  
  16.   
  17. int Floyd();  
  18.   
  19. int main()  
  20. {  
  21.     int t = 1;  
  22.     while (~scanf("%d", &n))  
  23.     {  
  24.         Init();  
  25.         if (n == 0) break;  
  26.         Read();  
  27.         printf("Case %d: ", t++);  
  28.         if (Floyd() == 1)  
  29.         {  
  30.             puts("Yes");  
  31.         }  
  32.         else  
  33.         {  
  34.             puts("No");  
  35.         }  
  36.     }  
  37.     return 0;  
  38. }  
  39.   
  40. void Init()  
  41. {  
  42.     int i, j;  
  43.     for (i=0; i<N; ++i)  
  44.     {  
  45.         for (j=0; j<N; ++j)  
  46.         {  
  47.             map[i][j] = 0;      //0则代表不能转换  
  48.         }  
  49.     }  
  50.     return;  
  51. }  
  52.   
  53. void Read()  
  54. {  
  55.     int i;  
  56.     char sa[N], sb[N];  
  57.     double x;  
  58.     for (i=0; i<n; ++i)  
  59.     {  
  60.         scanf("%s", str[i]);  
  61.     }  
  62.     scanf("%d", &m);  
  63.     for (i=0; i<m; ++i)  
  64.     {  
  65.         scanf("%s %lf %s", sa, &x, sb);  
  66.         map[Count(sa)][Count(sb)] = x;  
  67.     }  
  68.     return;  
  69. }  
  70.   
  71. int Count(char s[])     //计算字符串编号  
  72. {  
  73.     int i;  
  74.     for (i=0; i<n; ++i)  
  75.     {  
  76.         if (strcmp(s, str[i]) == 0)  
  77.         {  
  78.             return i;  
  79.         }  
  80.     }  
  81.     return -1;  
  82. }  
  83.   
  84. int Floyd()  
  85. {  
  86.     int i, j, k;  
  87.     for (k=0; k<n; ++k)  
  88.     {  
  89.         for (i=0; i<n; ++i)  
  90.         {  
  91.             for (j=0; j<n; ++j)  
  92.             {  
  93.                 map[i][j] = Max(map[i][j], map[i][k] * map[k][j]);  
  94.             }  
  95.         }  
  96.     }  
  97.     for (j=0; j<n; ++j)     //检验判断是否存在套利  
  98.     {  
  99.         if (map[j][j] > 1)  
  100.         {  
  101.             return 1;  
  102.         }  
  103.     }  
  104.     return 0;  
  105. }  

相关推荐