Input
套利是指利用货币汇率的差异，将一种货币的一个单位转换为同一货币的多个单位。例如，假设1美元买0.5英镑，1英镑买10.0法国法郎，1法国法郎买0.21美元。然后，通过兑换货币，聪明的交易者可以从1美元开始，购买0.5 x 10.0 x 0.21 = 1.05美元，获得5%的利润。
您的工作是编写一个程序，以货币汇率列表作为输入，然后确定是否可能进行套利。
Output
输入将包含一个或多个测试用例。每个测试用例的第一行有一个整数n (1<=n<=30)，表示不同货币的数量。接下来的n行每一行都包含一种货币的名称。名称中不会出现空格。下一行包含一个整数m，表示接下来的表的长度。最后的m行分别包含源货币的名称ci、表示从ci到cj的汇率的实数rij和目标货币的名称cj。没有出现在表格中的交易是不可能的。
测试用例通过空行彼此分开。对于n，输入以0(0)的值结束。
Sample Input
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
Sample Output
Case 1: Yes
Case 2: No
题目大意：
首先输入了一个 n ，表示有 n 个币种，接下来输入m种转换方式，每种输入币种a，汇率c 和币种b，说明a -> b 的汇率是 b，依照题意，1英镑买10.0法国法郎，1法国法郎买0.21美元。然后，通过兑换货币，聪明的交易者可以从1美元开始，购买0.5 x 10.0 x 0.21 = 1.05美元，判断是否可以通过货币转换来实现套现。
解题思路：
抽象成图论问题，套现即找变大环，因为题目没有指定手中现有的货币，所以从1 - n 依次跑spfa判正环即可，建图的时候注意一下，这里输入的是字符串，通过map映射一下 ，映射成地图下标，再跑spfa即可。
Code：
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define lowbit(x) x & (-x)using namespace std;typedef long long ll;
typedef pair<int, int> pii;const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 1e3 + 50;
const int M = 1e4 + 50;int h[N], ne[M], e[M], idx;
int n, m;
double dis[N], w[M];
int cnt[N];
bool vis[N];void add(int a, int b, double c)
{
e[idx] = b;w[idx] = c;ne[idx] = h[a];h[a] = idx++;
}void init()//多组输入，注意初始化
{
idx = 0;memset(h, -1, sizeof h);
}
bool spfa(int s)//依次跑spfa判变大环
{
queue<int > q;for (int i = 1; i <= n; i ++){
dis[i] = 0;vis[i] = false;}q.push(s);vis[s] = true;dis[s] = 1;while (!q.empty()){
int t = q.front();q.pop();vis[t] = false;for (int i = h[t]; ~i; i = ne[i]){
int j = e[i];if (dis[t] * w[i] > dis[j]){
dis[j] = dis[t] * w[i];cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true;if (!vis[j]){
q.push(j);vis[j] = true;}}}}return false;
}int main()
{
int c = 1;while (scanf("%d", &n) && n){
init();map<string, int> mp;string s;for (int i = 1; i <= n; i ++)//借助map映射成整数下标{
cin >> s;mp[s] = i;}scanf("%d", &m);while (m --){
string a, b;double c;cin >> a >> c >> b;add(mp[a], mp[b], c);//建图的过程}bool flag = false;for (int i = 1; i <= n; i ++){
memset(cnt, 0, sizeof cnt);flag = spfa(i);if (flag) break;}printf("Case %d: %s\n", c ++, flag ? "Yes" : "No");}return 0;
}