hdu1217Arbitrage(floyd+map)

Arbitrage

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10439 Accepted Submission(s): 4721

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

USDollar

BritishPound

FrenchFranc

USDollar 0.5 BritishPound

BritishPound 10.0 FrenchFranc

FrenchFranc 0.21 USDollar

USDollar

BritishPound

FrenchFranc

USDollar 0.5 BritishPound

USDollar 4.9 FrenchFranc

BritishPound 10.0 FrenchFranc

BritishPound 1.99 USDollar

FrenchFranc 0.09 BritishPound

FrenchFranc 0.19 USDollar

Sample Output

Case 1: Yes

Case 2: No

题意：给出钱的种类。再给出每两种钱的换算比率。一开始只有1美元，问通过不同钱币之间转换最后能不能赚钱。

题解：因为输入的钱币种类是字符串，要用map转换一下，变成方便计算的数字编号。存起来用floyd算法跑一遍，最后看a[1][1]是不是比1大，如果最后比1大，就说明赚钱了。注意：初始化数组将a[1]a[1]设为1，其他设为0.因为是double数组，所以不要用memset去初始化。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 double a[40][40];
 5 map<string,int>s;
 6 void init()
 7 {
 8     for(int i=0;i<40;i++)
 9     {
10         for(int j=0;j<40;j++)
11         {
12             a[i][j]=0;
13         }
14     }
15     a[1][1]=1.0;
16 }
17 bool floyd()
18 {
19     for(int k=1;k<=n;k++)
20     {
21         for(int i=1;i<=n;i++)
22         {
23             for(int j=1;j<=n;j++)
24             {
25                 a[i][j]=max(a[i][j],a[i][k]*a[k][j]*1.0);
26                 
27             }
28         }
29     }
30     if(a[1][1]>1.0)return true;
31     return false;
32 }
33 int cases=0;
34 int main() {
35     while(~scanf("%d",&n),n)
36     {
37         init();
38         cases++;
39         //int num=0;
40         for(int i=1;i<=n;i++)//字符串转换 
41         {
42             char temp[100];
43             scanf("%s",temp);
44             s[temp]=i;
45         }
46         scanf("%d",&m);
47         for(int i=0;i<m;i++)
48         {
49             char temp1[100],temp2[100];
50             double temp3;
51             scanf("%s %lf %s",temp1,&temp3,temp2);//存两种钱币的转换比率 
52             if(temp3>a[s[temp1]][s[temp2]])
53             a[s[temp1]][s[temp2]]=temp3;
54         }
55         if(floyd())printf("Case %d: Yes
",cases);
56         else printf("Case %d: No
",cases);
57         //printf("
");
58     }
59     return 0;
60 }