描述
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.
- 输入
- The input file 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. - 输出
- For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: 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 - 来源
- NKOJ or 1996/97 Ulm Internal Contest
- 上传者
- 苗栋栋
题意：给出一些货币和货币之间的兑换比率，问是否可以使某种货币经过一些列兑换之后，货币值增加。举例说就是1美元经过一些兑换之后，超过1美元。可以输出Yes，否则输出No。
AC代码:
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 111 double mp[MAX][MAX];
int n,m; void floyd()
{
for(int k=; k<=n; k++)
for(int i=; i<=n; i++)
for(int j=; j<=n; j++)
if(mp[i][j]< mp[i][k]*mp[k][j])
mp[i][j]=mp[i][k]*mp[k][j];
} void init()
{
for(int i=; i<=n; i++){
for(int j=; j<=n; j++){
if(i==j)
mp[i][j]=;
else
mp[i][j]=;
}
}
} int main()
{
int sum=;
double rate;
char a[],b[],c[];
while(~scanf("%d",&n)&&n){
init();
map<string,int> mmp;
for(int i=; i<=n; i++){
scanf("%s",a);
mmp[a]=i;
}
scanf("%d",&m);
for(int i=; i<=m; i++){
scanf("%s%lf%s",b,&rate,&c);
int x=mmp[b];
int y=mmp[c];
mp[x][y]=rate;
//printf("%d\n",mp[x][y]);
}
floyd();
int flag=;
for(int i=; i<=n; i++){
//printf("%d\n",mp[i][i]);
if(mp[i][i]>){
flag=;
break;
}
}
printf("Case %d: ",++sum);
printf("%s\n",flag ? "Yes" : "No");
}
}
SPFA:
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 111 int n, m;
double dis[MAX], mp[MAX][MAX];
struct node
{
char name[];
}a[MAX]; int find(char *s)
{
for(int i = ; i < n; i++)
if(strcmp(a[i].name, s) == )
return i;
} int SPFA(int p)
{
queue<int> q;
bool vis[MAX];
memset(dis,,sizeof(dis));
memset(vis, , sizeof(vis));
while(!q.empty())
q.pop();
dis[p] = ;
vis[p] = ;
q.push(p);
while(!q.empty())
{
int x = q.front();
q.pop();
vis[x] = false;
for(int i = ; i < n; i++)
{
if(dis[i] < dis[x] * mp[x][i])
{
dis[i] = dis[x] * mp[x][i];
if(dis[p] > 1.0)
return ;
if(!vis[i])
{
vis[i] = true;
q.push(i);
}
}
}
}
return ;
} int main()
{
int i, j, cas = ;
char s1[], s2[];
double s;
while(~scanf("%d",&n) && n)
{
for(i = ; i < n; i++)
{
for(j = ; j < n; j++)
{
if(i == j)
mp[i][j] = ;
else
mp[i][j] = ;
}
}
for(i = ; i < n; i++)
scanf("%s",a[i].name);
scanf("%d",&m);
for(i = ; i < m; i++)
{
scanf("%s%lf%s",s1, &s, s2);
int u = find(s1), v = find(s2);
mp[u][v] = s;
}
int flag = ;
for(i = ; i < n; i++)
{
if(SPFA(i) == )
{
flag = ;
break;
}
}
printf("Case %d: ",++cas);
printf("%s\n", flag ? "Yes" : "No");
}
return ;
}
Bellman_Ford代码(hdu 可过):
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 111 struct node
{
int x,y;
double rate;
}e[MAX]; int n,m,v;
bool flag;
double dis[MAX]; bool Bellman_Ford(int p)
{
memset(dis,,sizeof(dis));
dis[p]=;
for(int j=; j<n; j++)
for(int i=; i<v; i++)
{
if(dis[e[i].y] < dis[e[i].x] * e[i].rate)
dis[e[i].y] = dis[e[i].x] * e[i].rate;
}
//for(int i=0; i<v; i++)
// printf("%d\n",dis[e[i].y]);
for(int i = ; i<v; i++)
if(dis[e[i].y] < dis[e[i].x] * e[i].rate)
return true;
return false;
} int main()
{
int sum=;
char a[], b[], c[];
double rate;
while(~scanf("%d",&n)&&n){
v=;
map<string,int> mp;
for(int i=; i<=n; i++){
scanf("%s",a);
mp[a]=i;
}
scanf("%d",&m);
for(int i=; i<=m; i++){
scanf("%s%lf%s",b,&rate,c);
int x=mp[b];
int y=mp[c];
e[v].x=x;
e[v].y=y;
e[v++].rate=rate;
}
flag=Bellman_Ford();
if (flag)
printf("Case %d: Yes\n",++sum);
else
printf("Case %d: No\n", ++sum);
}
}