poj2240 Arbitrage

思路：

有向图判负环。

实现：

（1）spfa

 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 #include <cmath>
 5 #include <queue>
 6 using namespace std;
 7 const int INF = 0x3f3f3f3f;
 8 const int MAXN = 35;
 9 double G[MAXN][MAXN], d[MAXN];
10 bool in[MAXN];
11 int n, m, num[MAXN];
12 bool spfa(int s)
13 {
14     queue<int> q;
15     d[s] = 0;
16     q.push(s);
17     in[s] = true;
18     while (!q.empty())
19     {
20         int tmp = q.front(); q.pop();
21         in[tmp] = false;
22         for (int i = 0; i <= n; i++)
23         {
24             if (d[tmp] + G[tmp][i] < d[i])
25             {
26                 d[i] = d[tmp] + G[tmp][i];
27                 if (!in[i]) { in[i] = true; q.push(i); }
28                 num[i]++;
29                 if (num[i] > n) return true;
30             }
31         }
32     }
33     return false;
34 }
35 int main()
36 {
37     map<string, int> mp;
38     string s, t;
39     double x;
40     int Kase = 1;
41     while (cin >> n, n)
42     {
43         for (int i = 0; i <= n; i++)
44         {
45             for (int j = 0; j <= n; j++)
46             {
47                 G[i][j] = INF;
48             }
49         }
50         fill(d, d + n + 1, INF);
51         fill(in, in + n + 1, 0);
52         fill(num, num + n + 1, 0);
53         mp.clear();
54         for (int i = 1; i <= n; i++)
55         {
56             cin >> s;
57             mp[s] = i;
58         }
59         cin >> m;
60         for (int i = 1; i <= m; i++)
61         {
62             cin >> s >> x >> t;
63             G[mp[s]][mp[t]] = -log(x);
64         }
65         for (int i = 1; i <= n; i++) G[0][i] = 0;
66         cout << "Case " << Kase++ << ": ";
67         if (spfa(0)) cout << "Yes" << endl;
68         else cout << "No" << endl;
69     }
70     return 0;
71 }

（2）floyd

 1 #include <iostream>
 2 #include <map>
 3 #include <string>
 4 #include <cmath>
 5 using namespace std;
 6 const int INF = 0x3f3f3f3f;
 7 const int MAXN = 35;
 8 double G[MAXN][MAXN];
 9 int n, m;
10 
11 int main()
12 {
13     map<string, int> mp;
14     string s, t;
15     double x;
16     int Kase = 1;
17     while (cin >> n, n)
18     {
19         for (int i = 1; i <= n; i++)
20         {
21             for (int j = 1; j <= n; j++)
22             {
23                 if (i == j) G[i][j] = 0;
24                 else G[i][j] = INF;
25             }
26         }
27         mp.clear();
28         for (int i = 1; i <= n; i++)
29         {
30             cin >> s;
31             mp[s] = i;
32         }
33         cin >> m;
34         for (int i = 1; i <= m; i++)
35         {
36             cin >> s >> x >> t;
37             G[mp[s]][mp[t]] = -log(x);
38         }
39         for (int k = 1; k <= n; k++)
40         {
41             for (int i = 1; i <= n; i++)
42             {
43                 for (int j = 1; j <= n; j++)
44                 {
45                     if (G[i][k] + G[k][j] < G[i][j])
46                         G[i][j] = G[i][k] + G[k][j];
47                 }
48             }
49         }
50         bool flg = false;
51         for (int i = 1; i <= n; i++)
52         {
53             if (G[i][i] < 0) { flg = true; break; }
54         }
55         cout << "Case " << Kase++ << ": ";
56         if (flg) cout << "Yes" << endl;
57         else cout << "No" << endl;
58     }
59     return 0;
60 }