1．链接地址
https://vjudge.net/problem/POJ-2240
2．问题描述
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.
Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
输入样例
3 USDollar BritishPound FrenchFranc 3 USDollar 0.5 BritishPound BritishPound 10.0 FrenchFranc FrenchFranc 0.21 USDollar 3 USDollar BritishPound FrenchFranc 6 USDollar 0.5 BritishPound USDollar 4.9 FrenchFranc BritishPound 10.0 FrenchFranc BritishPound 1.99 USDollar FrenchFranc 0.09 BritishPound FrenchFranc 0.19 USDollar 0
输出样例
Case 1: Yes Case 2: No
3．解题思路
求通过兑换货币的方式能不能实现盈利
其实就是一个判环，只要能通过兑换货币增长货币金额，说明存在环可以一直增加
4．算法实现源代码
#include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<iostream> #include<vector> #include<map> using namespace std; int n,m; double dist[40]; struct edge { int st,ed; double rt; edge(int sst,int eed,double rtt) : st(sst),ed(eed),rt(rtt) {} edge() {} }; vector<edge> G; map<string ,int> mp; bool Bellman_ford(int v) { memset(dist,0,sizeof(dist)); dist[v] = 1; for(int j = 1;j < n;j++) { for(int i = 0;i < G.size();i++) { int p1 = G[i].st,p2 = G[i].ed; if(dist[p2] < dist[p1] * G[i].rt) { dist[p2] = dist[p1] * G[i].rt; } } } for(int i = 0;i < G.size();i++) { int p1 = G[i].st,p2 = G[i].ed; if(dist[p2] < dist[p1] * G[i].rt) { return true; } } return false; } int main() { int cas = 1; string s,ss; while(~scanf("%d",&n) &&n) { for(int i = 0;i < n;i++) { cin >> s; mp[s] = i; } cin >> m; string beg,ends; double r; G.clear(); for(int i = 0;i < m;i++) { cin >> beg >> r >> ends; G.push_back(edge (mp[beg] ,mp[ends] ,r) ); } printf("Case %d: ",cas++); for(int i = 0;i < n;i++) { if(Bellman_ford(i)) { cout << "Yes" << endl; break; } else if(i == n - 1) cout << "No" <<endl; } } return 0; }
原文：https://www.cnblogs.com/KasenBob/p/11438698.html