POJ 2240 Arbitrage（判正环）

题意：
货币兑换，判断最否是否能获利。

思路：
又是货币兑换题，Belloman-ford和floyd算法都可以的。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<map>
 6 using namespace std;
 7 
 8 const int maxn = 1000 + 5;
 9 
10 int n, m;
11 string s1,s2;
12 
13 map<string, int> p;
14 
15 struct
16 {
17     int u, v;
18     double rate;
19 }edge[maxn];
20 
21 double d[40];
22 
23 bool bellman(int s)
24 {
25     memset(d, 0, sizeof(d));
26     d[s] = 1;
27     for (int i = 1; i < n; i++)
28     {
29         bool flag = false;
30         for (int j = 0; j < m; j++)
31         {
32             if (d[edge[j].v] < d[edge[j].u] * edge[j].rate)
33             {
34                 d[edge[j].v] = d[edge[j].u] * edge[j].rate;
35                 flag = true;
36             }
37         }
38         if (!flag)  break;
39     }
40     for (int j = 0; j < m; j++)
41         if(d[edge[j].v] < d[edge[j].u] * edge[j].rate)
42         return true;
43     return false;
44 }
45 
46 int main()
47 {
48     ios::sync_with_stdio(false);
49     //freopen("D:\txt.txt", "r", stdin);
50     double r;
51     int kase = 0;
52     while (~scanf("%d", &n) && n)
53     {
54         for (int i = 0; i < n; i++)
55         {
56             cin >> s1;
57             p[s1] = i;
58         }
59         scanf("%d", &m);
60         for (int i = 0; i < m; i++)
61         {
62             cin >> s1 >> r >> s2;
63             edge[i].u = p[s1];
64             edge[i].v = p[s2];
65             edge[i].rate = r;
66         }
67         printf("Case %d: ", ++kase);
68         bool flag = false;
69         for (int i = 0; i < n; i++)
70         {
71             if (bellman(i))
72             {
73                 printf("Yes
");
74                 flag = true;
75                 break;
76             }
77         }
78         if (!flag)
79             printf("No
");
80     }
81     return 0;
82 }

Belloman-ford

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<map>
 6 using namespace std;
 7 
 8 const int maxn = 1000 + 5;
 9 const int INF = 10000;
10 
11 int n, m;
12 string s1,s2;
13 
14 map<string, int> p;
15 
16 double d[maxn][maxn];
17 
18 void floyd()
19 {
20     for (int k = 0; k < n; k++)
21     for (int i = 0; i < n; i++)
22     for (int j = 0; j < n; j++)
23         d[i][j] = max(d[i][j], d[i][k] * d[k][j]);        
24 }
25 
26 int main()
27 {
28     ios::sync_with_stdio(false);
29     //freopen("D:\txt.txt", "r", stdin);
30     double r;
31     int kase = 0;
32     while (~scanf("%d", &n) && n)
33     {
34         memset(d, INF, sizeof(d));
35         for (int i = 0; i < n; i++)
36         {
37             cin >> s1;
38             p[s1] = i;
39             d[i][i] = 1;   //一开始的汇率为1
40         }
41         scanf("%d", &m);
42         for (int i = 0; i < m; i++)
43         {
44             cin >> s1 >> r >> s2;
45             d[p[s1]][p[s2]] = r;
46         }
47         floyd();
48         printf("Case %d: ", ++kase);
49         bool flag = false;
50         for (int i = 0; i < n; i++)
51         {
52             if (d[i][i]>1)   //如果自身汇率大于1，说明可以套利
53             { 
54                 printf("Yes
");
55                 flag = true;
56                 break;
57             }
58         }
59         if (!flag)
60             printf("No
");
61     }
62     return 0;
63 }

floyd