Arbitrage

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 43 Accepted Submission(s) : 16

Problem Description

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.

Input

The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.<br>Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

Sample Input

3USDollarBritishPoundFrenchFranc3USDollar 0.5 BritishPoundBritishPound 10.0 FrenchFrancFrenchFranc 0.21 USDollar3USDollarBritishPoundFrenchFranc6USDollar 0.5 BritishPoundUSDollar 4.9 FrenchFrancBritishPound 10.0 FrenchFrancBritishPound 1.99 USDollarFrenchFranc 0.09 BritishPoundFrenchFranc 0.19 USDollar0

Sample Output

Case 1: YesCase 2: No

Source

PKU

题意：给出一些货币和货币之间的兑换比率，问是否可以使某种货币经过一些列兑换之后，货币值增加。举例说就是1美元经过一些兑换之后，超过1美元。可以输出Yes，否则输出No。

思路：

其实每种货币可以看成一个点，货币之间的汇率看成这两点构成的边的权值，构造好图之后就是求从一点出发，看经过几条路径之后可以得到比自身大的值（但是注意路径上的权值是相乘的关系不是相加）。

用floyed算法，因为最多30种货币，所以用Flayd算法,Floyd算法的思想也比较好理解，主要就是图的构造,需要注意的是，题目要求最大汇率关系，所以更新数据时是求大于本身的，并且权值为相乘关系。

代码：

#include 
   
    #include 
    
     #include 
     #include 
      
       #include 
       
        using namespace std;map
        
         name; //map用来存储名称和编号double g[35][35]; //存储某两点的最大汇率。bool flag; //判断标志int main(){ int n,i,j,m,k; string str2,str1; double rate; int cas=0; while(scanf("%d",&n),n) //输入货币种类 { cas++; for(i=1;i<=n;i++) { cin>>str1; //输入名称，并记录下来编号 name[str1]=i; } for(i=1;i<=n;i++) //初始化，注意相同的货币之间汇率为1 for(j=1;j<=n;j++) { if(i==j)g[i][j]=1; else g[i][j]=0; } scanf("%d",&m); while(m--) { cin>>str1>>rate>>str2; g[name[str1]][name[str2]]=rate; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(g[i][j]
         
          1){flag=1;break;}//发现有超过汇率为1的即会超过本事，则更改标志 if(flag) printf("Case %d: Yes\n",cas); else printf("Case %d: No\n",cas); } return 0;}

转载地址：https://blog.csdn.net/sinat_37668729/article/details/76944224 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：8月8日训练笔记

下一篇：昂贵的聘礼（dfs）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

Arbitrage

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other)

Total Submission(s) : 43 Accepted Submission(s) : 16

发表评论

最新留言

关于作者

推荐文章