POJ 2240 Arbitrage(最短路 Floyd)

Arbitrage


大意:

给你m种货币,给你m种货币兑换规则,问通过这些规则最后能不能盈利。eg:1美元换0.5英镑,1英镑换10法郎,1法郎换0.21美元,这样1美元能换0.5*10*0.21=1.05美元,净赚0.05美元。

思路:

用Floyd找出每两种钱之间的最大兑换关系,遍历一遍,看有没有那种钱币最后能盈利,有就输出Yes,没有就是No。在处理钱币名称与编号之间的关系时,可以用map存(比较好用),当然也可以用字符串比较。


#include <stdio.h>
#include <iostream>
#include <map>
#define INF 0x3f3f3f3f
using namespace std;

char money[30];
char change1[30], change2[30];
double trans;
double Map[50][50];
int n, m;
///用map建立字符串与编号之间的关系
map<string, int>p;

void Floyd()
{
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                ///变形的最大路径  把‘+’变为了‘*’
                if(Map[i][j] < Map[i][k]*Map[k][j])
                {
                    Map[i][j] = Map[i][k]*Map[k][j];
                }
            }
        }
    }
    return ;
}

void Solve()
{
    int cnt = 1;
    while(~scanf("%d%*c", &n) && n)
    {
        for(int i = 1; i <= n; i++)
        {
            scanf("%s", money);
            p[money] = i;
            Map[i][i] = 1;
        }
        scanf("%d%*c", &m);
        for(int i = 1; i <= m; i++)
        {
            scanf("%s%lf%s", change1, &trans, change2);
            Map[p[change1]][p[change2]] = trans; ///去map中的数据建图
        }
        Floyd();
        bool flag = false;
        for(int i = 1; i <= n; i++)
        {
            if(Map[i][i] > 1)
            {
                flag = true;
                break;
            }
        }
        if(flag)
        {
            printf("Case %d: Yes\n", cnt++);
        }
        else
        {
            printf("Case %d: No\n", cnt++);
        }
    }
}

int main()
{
    Solve();

    return 0;
}


POJ 2240 Arbitrage(最短路 Floyd)

上一篇:Excel-时间序列图(趋势)分析


下一篇:UFLDL学习笔记(6)