ZOJ 1092 Arbitrage

时间:2022-02-21 11:12:28

原题链接

题目大意:Arbitrage这个单词的解释是“套利交易”,就是利用几个币种之间的汇率差价来赚钱。比如人民币兑美元6:1,美元兑欧元1.5:1,欧元兑人民币10:1,那么用9元人民币可以换1.5美元,1.5美元换1欧元,1欧元换10元人民币。这样一倒手,就赚了1元。这是闷声发大财的典型例子!

解法:在做这道题的时候,又学会了一种新的算法(Floyd算法)。具体过程是开辟一个方阵,每行每列都对应一种货币,每个元素就是横纵两种货币的汇率。然后是一个三层循环,最外层的循环是表示过度节点的,这一层必须放在最外面,里面两层是行和列的扫描。如果经过某一个过渡点汇率增加了,就更新这个节点。这里还要注意一个地方,字符串的比较,直接“==”就完蛋了,要用strcmp(str1,str2)==0来比较。

参考代码:

#include<iostream>
#include<string>
using namespace std; int main(){
int i,j,k,m,n,cases=0;
string str1,str2;
double t; while(cin>>n&&n!=0){
cases++;
string currency[30];
double table[30][30]={0.0}; //must use a constant value to initiate an array
for(i=0;i<n;i++){
cin>>currency[i];
table[i][i]=1;
}
cin>>m;
for(i=0;i<m;i++){
cin>>str1>>t>>str2;
j=0;
while(j<n){
if(str1.compare(currency[j])==0)
break;
j++;
}
k=0;
while(k<n){
if(str2.compare(currency[k])==0)
break;
k++;
}
table[j][k]=t;
}
for(k=0;k<n;k++){
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(table[i][k]*table[k][j]>table[i][j])
table[i][j]=table[i][k]*table[k][j];
}
}
}
bool flag=0;
for(i=0;i<n;i++){
if(table[i][i]>1){
cout<<"Case "<<cases<<": Yes"<<endl;
flag=1;
break;
}
}
if(flag==0)
cout<<"Case "<<cases<<": No"<<endl; } return 0;
} /*
blog.csdn.net/zxy_snow/article/details/5810890 For k←1 to n do // k为“媒介节点”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径?
dist(i,j) = dist(i,k) + dist(k,j)
*/