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
", c ++, flag ? "Yes" : "No");
}
return 0;
}