IT博客汇 | POJ-2240 解题报告

POJ-2240 解题报告

林达意发表于 2012-10-11 10:49:41

题意简述

输入货币名称以及货币间的汇率（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

mapSTL;

使用时，读入阶段给每个字符串标号：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
#include
#include

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<=1) return 0;
            else return 1;
    }
    return 1;
}

int main()
{
    mapSTL;
    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>str1>>e[i].r>>str2;
            e[i].a=STL[str1];
            e[i].b=STL[str2];
        }
        if(bellman_ford(m,e))
            cout<<"Case "<<<": Yes"<<<"Case "<<<": No"<

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

#include
#include
#include

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<=1) return 0;
            else return 1;
    }
    return 1;
}

int main()
{
    mapSTL;
    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>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 "<<<": Yes"<<<"Case "<<<": No"<