Dayi Lin, Ph.D.

Staff Researcher, AI & Software Engineering

POJ-2240 解题报告

POJ

题意简述

输入货币名称以及货币间的汇率(A到B的汇率可能与B到A的不同),判断是否有可能实现套汇(即从某指定货币开始,通过一系列的货币兑换操作,最终换回某货币并实现盈利)。

问题有多组数据,对于每组数据,第一行代表货币类别数量,第二行起的n行为各货币名称;接下来一行是允许的兑换方式总数,而后每行有三个部分,第一个和第三个分别是原始货币和兑换后货币的名称,第二个是汇率。数据的输入以0结束。

对于每组数据,输出是否可能实现套汇(YES或NO)。

例如:

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

输出:

Case 1: Yes
Case 2: No

算法分析

这也是一题典型的套汇问题,与POJ-1860有相似之处(《POJ-1860 解题报告》)。

套汇问题的典型解决思路是Bellman Ford算法的逆用。Bellman Ford的一大特点是能够在找最短路过程中发现负权环。在套汇问题中,情况恰好是相反的。我们需要利用Bellman Ford算法寻找正权环。原始Bellman Ford的边权松弛过程,是松弛的更短,因而初始时将原点到任意点的距离设为无穷大。对于套汇问题,边权松弛明显是越松弛越长,所以初值全部置为0。原点到每个点的距离d[i]即从原点代表的货币到该货币能换到的最大值。若经过松弛,能实现原点到自身的距离d[原点]>初始值,则说明实现了盈利。

标准的Bellman Ford算法是松弛V-1次,但对于套汇问题,因为一轮盈利值可能很小,又因为实数比较的不稳定性,所以可能需要松弛若干次才能比较出原点到自身距离的变化。松弛的次数是无法估计的。所以我们将原先的for循环控制改为while,终止条件即判断d[原点]是否大于初始值。为方便,我们将初始值设为1。

但这样一来,一旦不存在正权环(即无法盈利),则会陷入死循环。为避免死循环,我们增加标记位flag,每轮松弛开始前置为0,一旦发生松弛则置1。一轮松弛后若flag仍为0,且d[原点]并没有大于初始值,则可判断图已没法松弛且不存在正权环。直接返回无法盈利。

套汇问题中Bellman Ford的松弛规则,就是题目描述的套汇规则。本题是直接乘以汇率,1860还需减去手续费。

实现时,以第一种货币为原点。最后判断d[1]。

Problem Status: AC。时间766ms,内存784k

细节

关于货币名与标号对应,可以利用C++中的容器,建立字符串到整型的一一对应关系。

#include<map>
map<string,int>STL;

使用时,读入阶段给每个字符串标号:STL[str]=i;

调用时,将STL[str1]作为整型数组下标使用即可。

特殊情况

这道题用Bellman Ford在POJ即可AC。但仔细考虑,不难发现Bellman Ford只适用于这张图是连通图的情况下。如果图是不连通的,而正权环恰巧不在第一个货币节点所在的那一部分,则无法发现正权环的存在。

我想到的第一个解决方法,是设立0号节点,建立这个点到每个节点的往返两条边,往返边权值均为1(代表走这条边不会盈利也不会亏损,不影响正权环寻找),这样整张图便成为了连通图。以0号点为原点,最后只需判断d[0]是否大于初始值即可。但调试发现,一旦图中任意一条边的权值大于1,则会返回YES。这个很好理解,假设A到B的权值大于1,则原点出发到A,A到B,B再返回原点,原点即实现了更新。但这并不能证明边AB是正权环的一部分。

为了解决这个情况,我想过把0号点到各节点的边改为单向,只出不入,但这样便无法更新d[0],没有起到连通全图的作用。

最终的解决方案是,从0号点出的边权值设为1,但返回的边权值设为一个极小的值。这样非正权环就无法对其更新,因为返回会消耗增加的部分。但正权环因为可以通过无限次的松弛达到无穷大,所以可以更新它。这种解决方案本机测试通过。

但为了达到足够更新原点的大小,正权环需要被松弛非常多次。这使得算法的时间复杂度一下变的非常高。因而这种算法提交POJ得到Runtime Error提示。

如何解决非连通图呢?

网上有一种思路是用Floyd算法变形。最后扫描全图每点到自身的距离是否被更新。只要有一点被更新则说明存在正权环。

程序样例(Bellman Ford)

#include<iostream>
#include<string>
#include<map>

using namespace std;

struct edge {
  int a;
  int b;
  double r;
};

int bellman_ford(int m, struct edge e[]) {
  double d[31] = {0};
  int flag, i;
  d[1] = 1;
  while (d[1] <= 1) {
    flag = 0;
    for (i = 0; i < m; i++)
      if (d[e[i].b] < d[e[i].a] * e[i].r) {
        flag = 1;
        d[e[i].b] = d[e[i].a] * e[i].r;
      }
    if (flag == 0)
      if (d[1] <= 1) return 0;
      else return 1;
  }
  return 1;
}

int main() {
  map < string, int > STL;
  int n, m, i, t, casei = 1;
  struct edge e[900];
  string str1, str2;
  while ((cin >> n) && (n != 0)) {
    for (i = 1; i <= n; i++) {
      cin >> str1;
      STL[str1] = i;
    }
    cin >> m;
    for (i = 0; i < m; i++) {
      cin >> str1 >> e[i].r >> str2;
      e[i].a = STL[str1];
      e[i].b = STL[str2];
    }
    if (bellman_ford(m, e))
      cout << "Case " << casei++ << ": Yes" << endl;
    else
      cout << "Case " << casei++ << ": No" << endl;
  }
  return 0;
}

程序样例(Bellman Ford修正非连通图)

#include<iostream>
#include<string>
#include<map>

using namespace std;

struct edge {
  int a;
  int b;
  double r;
};

int bellman_ford(int m, struct edge e[]) {
  double d[31] = {0};
  int flag, i;
  d[0] = 1;
  while (d[0] <= 1) {
    flag = 0;
    for (i = 0; i < m; i++)
      if (d[e[i].b] < d[e[i].a] * e[i].r) {
        flag = 1;
        d[e[i].b] = d[e[i].a] * e[i].r;
      }
    if (flag == 0)
      if (d[0] <= 1) return 0;
      else return 1;
  }
  return 1;
}

int main() {
  map < string, int > STL;
  int n, m, i, t, casei = 1;
  struct edge e[900];
  string str1, str2;
  while ((cin >> n) && (n != 0)) {
    for (i = 1; i <= n; i++) {
      cin >> str1;
      STL[str1] = i;
    }
    cin >> m;
    for (i = 0; i < m; i++) {
      cin >> str1 >> e[i].r >> str2;
      e[i].a = STL[str1];
      e[i].b = STL[str2];
    }
    for (t = 1; t <= n; t++) {
      e[i].a = 0;
      e[i].b = t;
      e[i].r = 1;
      i++;
      e[i].b = 0;
      e[i].a = t;
      e[i].r = 0.0000001;
      i++;
    }
    m = m + n * 2;
    if (bellman_ford(m, e))
      cout << "Case " << casei++ << ": Yes" << endl;
    else
      cout << "Case " << casei++ << ": No" << endl;
  }
  return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *