题意

给n种货币，m条货币之前的汇率，判断最后能否从中套利

解题思路

典型的判定负环图的问题，题目给的货币字符串，用map来给不同的字符串一个映射就可以了

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<vector>
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<set>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> PII;
const int maxn = 105;
const int maxm = 1e6+5;
const int inf = 1<<30;
struct Edge 
{
    int from,to;
    double cost;
    Edge(){}
    Edge(int a,int b,double c):from(a),to(b),cost(c){}
};
Edge E[maxm];
int N,M;
map<string,int> money;
double dis[maxn];
bool bellman_ford()
{
    for(int i=0;i<=N;i++){
        dis[i] = 0;
    }
    dis[0] = 1;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            Edge e = E[j];
            double t = dis[e.from] * e.cost;
            if(dis[e.to] < t){
                dis[e.to] = t;
                if(i==N-1)
                    return false;
            }
        }
    }
    return true;
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int Case = 1;
    while(cin >> N,N){
        money.clear();
        string s;
        for(int i=0;i<N;i++){
            cin >> s;
            money[s] = i;
        }
        cin >> M;
        double t;
        string s2;
        for(int i=0;i<M;i++){
            cin >> s >> t >> s2;
            E[i] = Edge(money[s],money[s2],t);
        }
        bool ok = bellman_ford();
        cout << "Case "<< Case++ << ": ";
        if(!ok){
            cout << "Yes" << endl;
        }else{
            cout << "No" << endl;
        }
    }
    
    return 0;
}