题意简述
输入货币名称以及货币间的汇率（A到B的汇率可能与B到A的不同），判断是否有可能实现套汇（即从某指定货币开始，通过一系列的货币兑换操作，最终换回某货币并实现盈利）。
问题有多组数据，对于每组数据，第一行代表货币类别数量，第二行起的n行为各货币名称；接下来一行是允许的兑换方式总数，而后每行有三个部分，第一个和第三个分别是原始货币和兑换后货币的名称，第二个是汇率。数据的输入以0结束。
对于每组数据，输出是否可能实现套汇（YES或NO）。
例如：
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
算法分析
这也是一题典型的套汇问题，与POJ-1860有相似之处（《POJ-1860 解题报告》）。
套汇问题的典型解决思路是Bellman Ford算法的逆用。Bellman Ford的一大特点是能够在找最短路过程中发现负权环。在套汇问题中，情况恰好是相反的。我们需要利用Bellman Ford算法寻找正权环。原始Bellman Ford的边权松弛过程，是松弛的更短，因而初始时将原点到任意点的距离设为无穷大。对于套汇问题，边权松弛明显是越松弛越长，所以初值全部置为0。原点到每个点的距离d[i]即从原点代表的货币到该货币能换到的最大值。若经过松弛，能实现原点到自身的距离d[原点]>初始值，则说明实现了盈利。
标准的Bellman Ford算法是松弛V-1次，但对于套汇问题，因为一轮盈利值可能很小，又因为实数比较的不稳定性，所以可能需要松弛若干次才能比较出原点到自身距离的变化。松弛的次数是无法估计的。所以我们将原先的for循环控制改为while，终止条件即判断d[原点]是否大于初始值。为方便，我们将初始值设为1。
但这样一来，一旦不存在正权环（即无法盈利），则会陷入死循环。为避免死循环，我们增加标记位flag，每轮松弛开始前置为0，一旦发生松弛则置1。一轮松弛后若flag仍为0，且d[原点]并没有大于初始值，则可判断图已没法松弛且不存在正权环。直接返回无法盈利。
套汇问题中Bellman Ford的松弛规则，就是题目描述的套汇规则。本题是直接乘以汇率，1860还需减去手续费。
实现时，以第一种货币为原点。最后判断d[1]。
Problem Status: AC。时间766ms，内存784k
细节
关于货币名与标号对应，可以利用C++中的容器，建立字符串到整型的一一对应关系。
#include<map> map<string,int>STL;
使用时，读入阶段给每个字符串标号：STL[str]=i;
调用时，将STL[str1]作为整型数组下标使用即可。
特殊情况
这道题用Bellman Ford在POJ即可AC。但仔细考虑，不难发现Bellman Ford只适用于这张图是连通图的情况下。如果图是不连通的，而正权环恰巧不在第一个货币节点所在的那一部分，则无法发现正权环的存在。
我想到的第一个解决方法，是设立0号节点，建立这个点到每个节点的往返两条边，往返边权值均为1（代表走这条边不会盈利也不会亏损，不影响正权环寻找），这样整张图便成为了连通图。以0号点为原点，最后只需判断d[0]是否大于初始值即可。但调试发现，一旦图中任意一条边的权值大于1，则会返回YES。这个很好理解，假设A到B的权值大于1，则原点出发到A，A到B，B再返回原点，原点即实现了更新。但这并不能证明边AB是正权环的一部分。
为了解决这个情况，我想过把0号点到各节点的边改为单向，只出不入，但这样便无法更新d[0]，没有起到连通全图的作用。
最终的解决方案是，从0号点出的边权值设为1，但返回的边权值设为一个极小的值。这样非正权环就无法对其更新，因为返回会消耗增加的部分。但正权环因为可以通过无限次的松弛达到无穷大，所以可以更新它。这种解决方案本机测试通过。
但为了达到足够更新原点的大小，正权环需要被松弛非常多次。这使得算法的时间复杂度一下变的非常高。因而这种算法提交POJ得到Runtime Error提示。
如何解决非连通图呢？
网上有一种思路是用Floyd算法变形。最后扫描全图每点到自身的距离是否被更新。只要有一点被更新则说明存在正权环。
程序样例(Bellman Ford)
#include<iostream>
#include<string>
#include<map>
using namespace std;
struct edge {
int a;
int b;
double r;
};
int bellman_ford(int m, struct edge e[]) {
double d[31] = {0};
int flag, i;
d[1] = 1;
while (d[1] <= 1) {
flag = 0;
for (i = 0; i < m; i++)
if (d[e[i].b] < d[e[i].a] * e[i].r) {
flag = 1;
d[e[i].b] = d[e[i].a] * e[i].r;
}
if (flag == 0)
if (d[1] <= 1) return 0;
else return 1;
}
return 1;
}
int main() {
map < string, int > STL;
int n, m, i, t, casei = 1;
struct edge e[900];
string str1, str2;
while ((cin >> n) && (n != 0)) {
for (i = 1; i <= n; i++) {
cin >> str1;
STL[str1] = i;
}
cin >> m;
for (i = 0; i < m; i++) {
cin >> str1 >> e[i].r >> str2;
e[i].a = STL[str1];
e[i].b = STL[str2];
}
if (bellman_ford(m, e))
cout << "Case " << casei++ << ": Yes" << endl;
else
cout << "Case " << casei++ << ": No" << endl;
}
return 0;
}程序样例(Bellman Ford修正非连通图)
#include<iostream>
#include<string>
#include<map>
using namespace std;
struct edge {
int a;
int b;
double r;
};
int bellman_ford(int m, struct edge e[]) {
double d[31] = {0};
int flag, i;
d[0] = 1;
while (d[0] <= 1) {
flag = 0;
for (i = 0; i < m; i++)
if (d[e[i].b] < d[e[i].a] * e[i].r) {
flag = 1;
d[e[i].b] = d[e[i].a] * e[i].r;
}
if (flag == 0)
if (d[0] <= 1) return 0;
else return 1;
}
return 1;
}
int main() {
map < string, int > STL;
int n, m, i, t, casei = 1;
struct edge e[900];
string str1, str2;
while ((cin >> n) && (n != 0)) {
for (i = 1; i <= n; i++) {
cin >> str1;
STL[str1] = i;
}
cin >> m;
for (i = 0; i < m; i++) {
cin >> str1 >> e[i].r >> str2;
e[i].a = STL[str1];
e[i].b = STL[str2];
}
for (t = 1; t <= n; t++) {
e[i].a = 0;
e[i].b = t;
e[i].r = 1;
i++;
e[i].b = 0;
e[i].a = t;
e[i].r = 0.0000001;
i++;
}
m = m + n * 2;
if (bellman_ford(m, e))
cout << "Case " << casei++ << ": Yes" << endl;
else
cout << "Case " << casei++ << ": No" << endl;
}
return 0;
}