【POJ】2240 Arbitrage

题意：n种国家的货币，m个换算汇率。问你能不能赚钱。

eg：1美元换0.5英镑，1英镑换10法郎，1法郎换0.21美元，这样1美元能换0.5*10*0.21=1.05美元，净赚0.05美元。

题解：floyd跑的时候改成乘法运算。然后就是在货币上做一个map的映射。

代码：

 1 #include <iostream>
 2 #include <string>
 3 #include <map>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 100+5;
 8 const int inf = 0x3f3f3f;
 9 
10 map <string,int>mmp;
11 double mp[maxn][maxn];
12 
13 int n,m;
14 
15 void init(){
16     for(int i = 1; i <= n ;i++){
17         for(int j = 1; j <= n ;j++){
18             if(i == j){
19                 mp[i][j] = 1;
20             }
21             else{
22                 mp[i][j] = 0;
23             }
24         }
25     }
26 }
27 
28 void floyd(){
29     for(int k = 1; k <= n ;k++){
30         for(int i = 1; i <= n ;i++){
31             for(int j = 1; j <= n ; j++){
32                 mp[i][j] = max(mp[i][j] , mp[i][k] * mp[k][j]);
33                 //cout<<mp[i][j]<<endl;
34             }
35         }
36     }
37 }
38 
39 int main(){
40     int cas = 1;
41     while(cin>>n && n){
42         init();
43         string s;
44         for(int i = 1; i <= n ; i++){
45             cin>>s;
46             mmp[s] = i;
47         }
48 
49         cin>>m;
50         double rate;
51         string s1,s2;
52         for(int i = 0; i < m ;i++){
53             cin>>s1>>rate>>s2;
54             mp[ mmp[s1] ][ mmp[s2] ] = rate;
55         }
56         floyd();
57         int flag = 0;
58         for(int i =  1; i <= n ;i++){
59             if(mp[i][i] > 1){
60                 flag = 1;
61                 break;
62             }
63         }
64         if(flag)    printf("Case %d: Yes
",cas++);
65         else    printf("Case %d: No
",cas++);
66 
67     }
68 
69     
70     return 0;
71 }