POJ 2240 Arbitrage(Floyd)

POJ 2240 Arbitrage(Floyd)

http://poj.org/problem?id=2240

题意:给你一些货币比如A,B,C,然后给你他们之间存在的对换关系,如A可以换0.5个B,B可以换10个C,C可以换2个A等.然后问你是否存在一种对换可以使得1个A可以换到大于1个A的钱.

分析:

首先把每个货币的单词映射成一个数字,表示该货币的编号.然后其实本题用到了类似Floyd的动态规划思想.

首先假设货币1对换货币2 比率为a,货币2对换货币3 比率为b.

那么货币1对换货币3比率为多少呢? 为a*b.

现在我们希望货币能增值,所以如果货币1换货币3 有两种比率分别为0,5和0,6.那么我们明显放弃0.5那个,只需要用0.6的比率即可.所以这道题就成了求一个有向图的任意两点的最大兑换比例,不过这个比例不是相加运算了,而是相乘运算.

且现在不是最小值最优了,而是最大值最优了. 其实原理就是Floyd的动态规划原理.其实就是传递闭包,证明省略,可以参考Floyd的证明过程.

AC代码:

#include<cstdio>
#include<map>
#include<iostream>
#include<string>
using namespace std;
const int maxn= 30+5;
int n,m;
double d[maxn][maxn];
void init()
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            d[i][j]= i==j?1.0:0;    //为0则表示不可兑换
}
void floyd()
{
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                if(d[i][j] < d[i][k] * d[k][j])
                    d[i][j] = d[i][k]*d[k][j];
}
int main()
{
    int kase=0;
    while(scanf("%d",&n)==1&&n)
    {
        map<string,int> mp;
        for(int i=0;i<n;i++)
        {
            string s;
            cin>>s;
            mp[s]=i;
        }
        init();

        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            string s1,s2;
            double val;
            cin>>s1>>val>>s2;
            d[mp[s1]][mp[s2]] = val;
        }

        floyd();
        int i;
        for(i=0;i<n;i++)
            if(d[i][i]>1.0) break;
        if(i==n) printf("Case %d: No\n",++kase);
        else printf("Case %d: Yes\n",++kase);
    }
    return 0;
}