POJ-2240-Arbitrage
发布时间:2020-12-14 05:14:57 所属栏目:大数据 来源:网络整理
导读:链接:https://vjudge.net/problem/POJ-2240 题意: 给n种货币,和m种货币汇率。 问能否通过汇率是总金额增加。 思路: 和POJ-1860相同,都是求正权回路。此题货币由字符串给出,所以可以用map记录字符串对应的标号。 操作方便。 代码: #include iostream#i
链接:https://vjudge.net/problem/POJ-2240题意:给n种货币,和m种货币汇率。 问能否通过汇率是总金额增加。 思路:和POJ-1860相同,都是求正权回路。此题货币由字符串给出,所以可以用map记录字符串对应的标号。 操作方便。 代码:#include <iostream> #include <memory.h> #include <string> #include <istream> #include <sstream> #include <vector> #include <stack> #include <algorithm> #include <map> using namespace std; const int MAXN = 30+5; struct Node { int l,r; double rate; }node[MAXN*MAXN]; double Dis[MAXN]; int n,m; map<string,int> name; bool bellman_ford() { memset(Dis,sizeof(Dis)); Dis[1] = 1; for (int i = 1;i<=n-1;i++) { bool flag = false; for (int j = 1; j <= m; j++) if (Dis[node[j].r] < Dis[node[j].l] * node[j].rate) { Dis[node[j].r] = Dis[node[j].l] * node[j].rate; flag = true; } if (!flag) break; } for (int i = 1;i <= m;i++) if (Dis[node[i].r] < Dis[node[i].l] * node[i].rate) return true; return false; } int main() { string s; double rate; int cnt = 0; while (cin >> n&&n) { for (int i = 1;i<=n;i++) { cin >> s; name[s] = i; } cin >> m; for (int i = 1;i<=m;i++) { cin >> s; node[i].l = name[s]; cin >> rate; node[i].rate = rate; cin >> s; node[i].r = name[s]; } if (bellman_ford()) printf("Case %d: Yesn",++cnt); else printf("Case %d: Non",++cnt); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |