HDOJ1217——Floyd + Map

Problem Description

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.

套利，如果一种货币在经过多次汇率转换后变多了，说明能够套利。给出n种货币和m个货币的转换关系，问是否可以套利。

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也可能低于1，Dijkstra是不可用的，因为它不能处理负权。考虑到数据规模比较小，用复杂度为$O(N^2)$的Floyd可以方便求解。

#include<iostream>
#include<map>
#include<string>
#include<cstring>
using namespace std;
const int inf = 0x3f3f3f3f;
int n,m,cnt;
double mat[32][32];
double max(int a,int b){return a>b?a:b;}
void init()
{
  for(int i=0;i<32;i++)
  for(int j=0;j<32;j++)
    mat[i][j] = 0;  //如果某种转换关系不通，则赋值为0
}

void floyd()
{
  for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        mat[i][j] = max(mat[i][j],mat[i][k] * mat[k][j]);}  //尽可能找出一条最优的路线

bool scan()  //搜索是否有可以套利的方法
{
  for(int i=1;i<=n;i++)
    if(mat[i][i] > 1) return true;  
  return false;
}

int main()
{
  map<string,int> name;
  double p;
  string a,b,str;
  while(cin >> n && n)
  {
    init();  //初始化
    name.clear();
    for(int i=1;i<=n;i++)
    {
      cin >> str;
      name[str] = i;
    }
    cin >> m;
    for(int i=1;i<=m;i++)
    {
      cin >> a >> p >> b;
      mat[name[a]][name[b]] = p;
    }
    floyd();
    if(scan())  cout << "Case " << ++cnt << ": " << "Yes" << endl;
    else cout << "Case " << ++cnt << ": " << "No" << endl;
  }
}