题意:每两种货币之间都有不同的汇率 如果换回自己最后是赚的 输出Yes 否则是No
因为最多只有三十种货币 所以用Floyd是可行的 与一般的最短路板子不同的地方 汇率是要乘而不是加 如果乘上一个小于1的数就会比之前小
将每种货币看作点 汇率建边 如果这两种货币不能兑换 就设为0 最后与自己判断是否大于1 如果是 则存在套利 如果不是就不存在
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm> using namespace std;
int n,m,x,y,id=;
double tmp;
char a[],b[];
char s[][];
double mp[][]; void floyd(){
int flag=;
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];
for(int i=;i<n;i++){
if(mp[i][i]>){
flag=;break;
}
}
if(flag) printf("Case %d: Yes\n",id);
else printf("Case %d: No\n",id);
id++;
} int main(){
while(~scanf("%d",&n)){
if(n==) break;
memset(mp,,sizeof(mp));
for(int i=;i<n;i++){
scanf("%s",s[i]);
}
scanf("%d",&m);
while(m--){
scanf("%s%lf%s",a,&tmp,&b);
for(int j=;j<n;j++){
if(strcmp(a,s[j])==){
x=j;
break;
}
}
for(int j=;j<n;j++){
if(strcmp(b,s[j])==){
y=j;
break;
}
}
mp[x][y]=tmp;
}
floyd();
}
return ;
}