参考文章：http://blog.csdn.net/kld1412/article/details/51498207

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.
Input
The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line telling whether arbitrage is possible or not in the format “Case case: Yes” respectively “Case case: No”.
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

有很多种外币，它们之间部分可以互相兑换，假如你有一个单位的某种货币，问是否可以通过有限次兑换回到当初你拥有的那种货币，使得最后得到的货币多于一个单位。例如：1美元换0.5英镑，1英镑换10法币，1法币换0.21美元。从1美元出发，兑换过程为：1×0.5×10×0.21=1.05＞1，所以该套利交易可行。
按题目意思可以抽象成一个带权有向图求“最长路径”，每次从一个点出发，经过一个环路再回到出发点，实现一次套利交易，所以检查每个点的所有环，直到找到一次可行的套利交易或者全部检查完都没有可行的套利交易。从这个想法出发去找所以的环实现起来很麻烦，所以把问题简化，可以想到，这道题类似求给定节点对的最短路径，那么我们可以借助Floyd算法来实现这一过程。

#include <iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<map>
using namespace std;
map<string,int>id;
double swa[99][99];//细节部分，数据类型注意
int n,m;
void fload()
{
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                swa[i][j] = max(swa[i][j],swa[i][k]*swa[k][j]);
            }
        }
    }
}
int main()
{
   // int n;
    int res = 0;
    while(cin>>n)
    {
        if(n==0)
            break;
        id.clear();
        string t1,t2;
        getchar();
        for(int i=1;i<=n;i++)
        {
            cin>>t1;
            id[t1] = i;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i==j)
                    swa[i][j] =1;
                else
                    swa[i][j] = 0;
            }
        }
       // int m;
        cin>>m;
        double t;
                getchar();
        for(int i=1;i<=m;i++)
        {
            cin>>t1>>t>>t2;
            swa[id[t1]][id[t2]] = t;
        }
        fload();
        int ok = 0;
        for(int i=1;i<=n;i++)
        {
            if(swa[i][i]>1.0)
                {
                    ok = 1;
                    break;
                }

        }
        res++;
        cout<<"Case "<<res<<": ";
        if(ok)
            printf("Yes\n");
        else
            printf("No\n");

    }
    return 0;
}