POJ 2240 Arbitrage-白红宇

POJ 2240 Arbitrage

阅读量：5021 次

发布时间：2019-06-12

本文共 1384 字，大约阅读时间需要 4 分钟。

用map建立从货币名称到序号的映射，看做节点，汇率则看做边权，是单向路。

用floyd，只不过这里把加号变成乘号，而且是两点间的最大值。最后求是否有这么一点，从该点出发，再回到该点，总的值大于1。

注意：不能使用dijaskra,因为增值的方法不一定是优先选择权值最大的路径，有可能是一开始的汇率小，但之后就大，总的乘积大于1.

　　　所以要用以动态规划为基本思想的floyd来做。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             using namespace std;map
             
               currency; //建立从货币名称到编号的映射double rate[1010][1010];//rate[i][j]表示i兑换j货币的汇率vector
              
                link[40];//link[i]表示i可以与哪些货币兑换int n,m,start;double r;char str1[101],str2[101];int cases=0;int main(){ while(scanf("%d",&n)!=EOF){ if(n==0) break; cases++; bool flag=false; for(int i=0;i<=n;i++) link[i].clear(); currency.clear(); memset(rate,0,sizeof(rate)); //memset(dis,maxn,sizeof(dis)); for(int i=1;i<=n;i++){ scanf("%s",str1); currency[str1]=i; } scanf("%d",&m); for(int i=1;i<=m;i++){ scanf("%s%lf%s",str1,&r,str2); int a=currency[str1]; int b=currency[str2]; rate[a][b]=r; link[a].push_back(b); } //floyd算法 for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ //尽可能使rate[i][j]大 if(rate[i][k]*rate[k][j]>rate[i][j]){ rate[i][j]=rate[i][k]*rate[k][j]; } } } } for(int i=1;i<=n;i++){ if(rate[i][i]>1){ flag=true; break; } } if(flag){ printf("Case %d: Yes\n",cases); } else{ printf("Case %d: No\n",cases); } } return 0;}

转载于:https://www.cnblogs.com/chenxiwenruo/p/3280489.html

你可能感兴趣的文章