套利问题，给出若干对货币兑换的汇率，求能否通过汇率兑换使钱越来越多
#include #include #include #include #include #include using namespace std; typedef long long ll; const int N = 50; map mp; int idx, n, m; double f[N][N]; int find(string &s) { if (mp.count(s)) return mp[s]; return mp[s] = ++idx; } void init() { mp.clear(); idx = 0; for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) f[i][j] = 0; } void floyd() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[i][j] = max(f[i][j], f[i][k] * f[k][j]); } int main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int t = 0; while(cin >> n, n) { init(); ++t; for (int i = 1; i <= n; i++) { string s; cin >> s; find(s); } cin >> m; while(m--) { string s1, s2; double x; cin >> s1 >> x >> s2; f[mp[s1]][mp[s2]] = x; } floyd(); bool flag = false; for (int i = 1; i <= n; i++) { if (f[i][i] > 1) { flag = true; break; } } cout << "Case " << t << ": "; cout << (flag ? "Yes" : "No") << endl; } return 0; }