套利
题目描述
套利是利用汇率差异实现货币增值。例如,1美元可以兑换0.5英镑、1英镑可以兑换10法郎、1法郎可以兑换0.21美元。接下来,一个聪明的交易商就可以从1美元开始,0.5 * 10.0 * 0.21 =1.05美元,获得了5%的利润。
你的任务是写一个程序,从输入文件读入汇率清单,然后决定套利是有可能的或没有可能的。
输入格式
输入文件包含多组数据,每组数据的第一行是一个整数n( 1<=n<=30 )。代表有多少种货币。接下来n行字符串,每行表示一种货币的名称(名称中不会出现空格)。下一行是一个整数m,约定了汇率表的长度。随后的m行中,每行有三部分组成。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. 每组数据之间空一行。当n=0时表示输入数据结束。
输出格式
第i组数据,输出Case i: 后,如果可以套利,输出Yes,否则输出No。
样例 #1
样例输入 #1
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
样例输出 #1
Case 1: Yes
Case 2: No
思路
这里是把我们之前做的题目把数字改成了字符串,其实本质上也一样,我们只要用map来装就行了。
代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;
const int N = 1e5;
double dist[N];
map<string,int>s;
int n,m;
bool st[N];
int e[N],ne[N],h[N],idx;
double w[N];
int cnt[N];
int T;
void add(int a,int b,double c){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool spfa(){
queue<int>q;
memset(st,0,sizeof st);
memset(dist,0,sizeof dist);
memset(cnt,0,sizeof cnt);
// dist[1]=1;
for(int i=1;i<=n;i++){
q.push(i);
st[i]=true;
dist[i]=1;
}
while(q.size()){
int t=q.front();
q.pop();
st[t]=false;
for(int i=h[t];~i;i=ne[i]){
int j=e[i];
if(dist[j]<dist[t]*w[i]){
dist[j]=dist[t]*w[i];
cnt[j]=cnt[t]+1;
if(!st[j]){
if(cnt[j]>=n)return false;
st[j]=true;
q.push(j);
}
}
}
}
return true;
}
int main(){
while(cin>>n,n){
s.clear();
idx=0;
memset(h,-1,sizeof h);
for(int i=1;i<=n;i++){
string a;
cin>>a;
s[a]=i;
}
cin>>m;
for(int i=1;i<=m;i++){
string pa,pb;
double x;
cin>>pa>>x>>pb;
int a=s[pa],b=s[pb];
// cout<<a<<" "<<b<<endl;
add(a,b,x);
// add(b,a,x);
}
if(!spfa()){
printf("Case %d: Yes\n",++T);
}else{
printf("Case %d: No\n",++T);
}
}
return 0;
}
标签:判环,idx,BritishPound,STL,FrenchFranc,int,spfa,include,USDollar
From: https://blog.csdn.net/m0_60738889/article/details/139131614