POJ-2240 解题报告

题意简述

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

[cpp]
#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;
}

[/cpp]

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

[cpp]
#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;
}

[/cpp]

Leave a Reply

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