POJ 2240 Arbitrage（最短路 Floyd）

大意：

给你m种货币，给你m种货币兑换规则，问通过这些规则最后能不能盈利。eg：1美元换0.5英镑，1英镑换10法郎，1法郎换0.21美元，这样1美元能换0.5*10*0.21=1.05美元，净赚0.05美元。

思路：

用Floyd找出每两种钱之间的最大兑换关系，遍历一遍，看有没有那种钱币最后能盈利，有就输出Yes，没有就是No。在处理钱币名称与编号之间的关系时，可以用map存（比较好用），当然也可以用字符串比较。

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <map>
 4 #define INF 0x3f3f3f3f
 5 using namespace std;
 6 
 7 char money[30];
 8 char change1[30], change2[30];
 9 double trans;
10 double Map[50][50];
11 int n, m;
12 ///用map建立字符串与编号之间的关系
13 map<string, int>p;
14 
15 void Floyd()
16 {
17     for(int k = 1; k <= n; k++)
18     {
19         for(int i = 1; i <= n; i++)
20         {
21             for(int j = 1; j <= n; j++)
22             {
23                 ///变形的最大路径  把‘+’变为了‘*’
24                 if(Map[i][j] < Map[i][k]*Map[k][j])
25                 {
26                     Map[i][j] = Map[i][k]*Map[k][j];
27                 }
28             }
29         }
30     }
31     return ;
32 }
33 
34 void Solve()
35 {
36     int cnt = 1;
37     while(~scanf("%d%*c", &n) && n)
38     {
39         for(int i = 1; i <= n; i++)
40         {
41             scanf("%s", money);
42             p[money] = i;
43             Map[i][i] = 1;
44         }
45         scanf("%d%*c", &m);
46         for(int i = 1; i <= m; i++)
47         {
48             scanf("%s%lf%s", change1, &trans, change2);
49             Map[p[change1]][p[change2]] = trans; ///去map中的数据建图
50         }
51         Floyd();
52         bool flag = false;
53         for(int i = 1; i <= n; i++)
54         {
55             if(Map[i][i] > 1)
56             {
57                 flag = true;
58                 break;
59             }
60         }
61         if(flag)
62         {
63             printf("Case %d: Yes
", cnt++);
64         }
65         else
66         {
67             printf("Case %d: No
", cnt++);
68         }
69     }
70 }
71 
72 int main()
73 {
74     Solve();
75 
76     return 0;
77 }

Arbitrage