Arbitrage

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 4790    Accepted Submission(s): 2183

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 file 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.

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

3 USDollar BritishPound FrenchFranc 3 USDollar 0.5 BritishPound BritishPound 10.0 FrenchFranc FrenchFranc 0.21 USDollar 3 USDollar BritishPound FrenchFranc 6 USDollar 0.5 BritishPound USDollar 4.9 FrenchFranc BritishPound 10.0 FrenchFranc BritishPound 1.99 USDollar FrenchFranc 0.09 BritishPound FrenchFranc 0.19 USDollar 0

 

Sample Output

Case 1: Yes Case 2: No

题目大意如下：

给你n种货币，然后货币与货币之间是有一定的汇率，并且假设每种货币的初始值为1，是否存在兑换方式使得A货币经过几次兑换后，价值大于1.

（Arbitrage：套汇是指利用不同外汇市场的外汇差价，在某一外汇市场上买进某种货币，同时在另一外汇市场上卖出该种货币，以赚取利润。）

一开始做这个题目的时候，只是想到能抽象成一副有向图。每一种货币代表一个结点，货币与货币之间连接的线表示汇率。

想用DFS，模拟这个兑换过程，改了一会最后也没改对。

后来看人说是一个最短路问题，我就更纳闷了，这和最短路有什么关系？

其实，这不是一个最短路的问题，但是整个货币兑换的过程，很像Floyd算法的求法。

只不过在更新结点的时候要改进一下，我们不是求最短路。

rate[i][j]存储i和j之间的汇率。也即边的权重。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 35using namespace std;double rate[maxn][maxn];//v1和v2之间的汇率char name[maxn][maxn];//货币名称bool vis[maxn];int n,m;queue
         
           Q;double Max(double x,double y){ return (x > y) ? x : y;}double Min(double x,double y){ return (x < y) ? x : y;}void init(){ memset(name,0,sizeof(name)); memset(rate,0,sizeof(rate));}bool Floyd(){ for(int k = 1 ; k <=n ; ++k) for(int i = 1 ; i <= n ; ++i) for(int j = 1 ; j <= n ; ++j) rate[i][j] = Max(rate[i][j],rate[i][k] * rate[k][j]); for(int i = 1 ; i <= n ; ++i) if(rate[i][i] > 1.0)//第i种货币经过一系列兑换后再度变成i种货币 return true; return false;}int main(){ double weight; char name1[maxn],name2[maxn]; int v1,v2; int cnt = 1; while(cin >> n){ if(n == 0) break; init(); memset(name1,0,sizeof(name1)); memset(name2,0,sizeof(name2)); for(int i = 1 ; i <= n ; ++i) cin >> name[i]; cin >> m; while(m--){//读入结点 cin >> name1 >> weight >> name2; for(int i = 1 ; i <= n ; ++i) if(strcmp(name[i],name1) == 0){ v1 = i; break; } for(int i = 1 ; i <= n ; ++i) if(strcmp(name[i],name2) == 0){ v2 = i; break; } rate[v1][v2] = weight; } printf("Case %d: ",cnt++); if(Floyd()) printf("Yes\n"); else printf("No\n"); } return 0;}