POJ2240 - c++编程基础 - 编程开发网

这个题目是最短路的变形。。下面我给两种解法。。

题目如下：

Language: Arbitrage

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 14627		Accepted: 6166

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.

Input

The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

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

Source

Ulm Local 1996

第一种解法是bellman-ford算法：

因为是地点与数字相对应，所以我选择了stl中的map，以前从来没有用过。

在bellomn-ford中首先进行第二阶段，如果出现d[y]

当这一阶段结束，则对所有的边重新检查一遍。如果再次出现d[y]

则说明商人钻钱成功。还有就是在d数组的定义上，因为物写int导致我查了

很久。。

代码如下

#include
#include
   
     #include
    
      #include
     
       using namespace std; int n,m; struct edge { int u,v; double w; }e[1000]; double d[40]; int bellmon_ford() { int i,k; int x,y; double rate; memset(d,0,sizeof(d)); d[1]=1; int cas=1; for(k=1;k
      
        mp; char kindmoney[100]; char st[100],en[100]; double rate; int cas=1; while(~scanf("%d",&n)&&n) { for(i=1;i<=n;i++) { scanf("%s",kindmoney); mp[kindmoney]=i; } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%s%lf%s",st,&rate,en); e[i].u=mp[st]; e[i].v=mp[en]; e[i].w=rate; } printf("Case %d: ",cas++); if(bellmon_ford()) printf("Yes\n"); else printf("No\n"); } }

第二种解法是floyd算法。前面的处理过程和bellman-ford没有什么区别，只是

用floyd扫一遍，确定所有的d值，然后检查d[i][i]是否大于1，如果大于1，说明

本金升值了。。则跳出循环。。

代码如下：

#include
  
   
#include
   
     #include
     #include
     
       #define maxn 200 using namespace std; double d[maxn][maxn]; int n,m; void floyd() { int i,j,k; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(d[i][j]
      
       mp; char kindmoney[100]; char st[100],en[100]; double val; int i,j,ok,cas=1; while(~scanf("%d",&n)&&n) { ok=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(i==j) d[i][j]=1;//自己到自己的汇率为1 else d[i][j]=-1000; } for(i=1;i<=n;i++) { scanf("%s",kindmoney); mp[kindmoney]=i; } scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%s%lf%s",st,&val,en); d[mp[st]][mp[en]]=val; } floyd(); for(i=1;i<=n;i++) { if(d[i][i]>1.0) ok=1; if(ok) break; } printf("Case %d: ",cas++); if(ok) printf("Yes\n"); else printf("No\n"); } }