poj 2240 Arbitrage
Arbitrage
题目链接:http://poj.org/PRoblem?id=2240
题目大意:几种货币之间汇率换算,问是否存在一种情况使得兑换了一圈回来,能盈利,也就是大于 1。
本题与 poj3259 极为相似,只不过本题目为乘,那个为加。
详见代码注释:
#include <iostream> #include <cstdio> #include<cstring> using namespace std; const double INF=0x3f3f3f3f; double dis[35][35]; int n,m; char a[35][50]; int f(char x[]) { for(int i=1;i<=n;i++) if(strcmp(x,a[i])==0) return i; } int main() { int index=0; int flag; char x[50],y[50]; double d; int a1,b1; while(scanf("%d",&n),n) { flag=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { dis[i][j]=0; //³õʼ»¯ ÎÞÇî ¸ÄΪÁË 0 } } for(int i=1;i<=n;i++) { dis[i][i]=1; //¶Ô½ÇÏ߸³³õÖµ 1 } for(int i=1;i<=n;i++) { scanf("%s",a[i]); } cin>>m; for(int i=0;i<m;i++) { scanf("%s %lf %s",x,&d,y); a1=f(x);b1=f(y); dis[a1][b1]=d; } for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (dis[i][j]<dis[i][k]*dis[k][j]) //ÔÏȵļӱäΪÁË³Ë dis[i][j]=dis[i][k]*dis[k][j]; for(int i=1;i<=n;i++) if(dis[i][i]>1.0) { flag=1; break; } if(flag) printf("Case %d: Yes\n",++index); else printf("Case %d: No\n",++index); } return 0; }