HDU 1217 Arbitrage（Floyd的应用）

　　给出一些国家之间的汇率，看看能否从中发现某些肮脏的......朋友交易。

这是Floyd的应用，dp思想，每次都选取最大值，最后看看自己跟自己的.....交易是否大于一。。。。

#include<iostream>

#include<cstring>

#include<queue>

#include<cstdio>

#include<map>

using namespace std;

#define exp 0.00000001

map<string,int>ma;

double dp[][];

bool Equal(double a,double b)

{

    if(a-b > exp) return true;

    return false;

}

int main()

{

    int n,ca = ;

    while(~scanf("%d",&n) && n)

    {

        string a;

        ma.clear();

        memset(dp,,sizeof(dp));

        for(int i = ;i <= n;i++)

        {

            cin >> a;

            ma[a] = i;

            dp[i][i] = ;

        }

        int m;

        scanf("%d",&m);

        for(int i = ;i <= m;i++)

        {

            string fr,to;

            int fr1,to1;

            double k;

            cin>>fr>>k>>to;

            fr1 = ma[fr],to1 = ma[to];

            dp[fr1][to1] = k;

        }

        for(int k = ;k <= n;k++)

        {

            for(int i = ;i <= n;i++)

            {

                for(int j = ;j <= n;j++)

                    dp[i][j] = max(dp[i][j],dp[i][k] * dp[k][j]);

            }

        }

        bool flag = true;

        for(int i = ;i <= n;i++)

        {

            if(Equal(dp[i][i],1.0))

            {

                flag = false;

                break;

            }

        }

        printf("Case %d: ",++ca);

        if(flag) printf("No\n");

        else printf("Yes\n");

    }

    return ;

}