POJ 2240 Arbitrage（floyd）

http://poj.org/problem?id=2240

题意：好吧，又是一个换钱的题：套利是利用货币汇率的差异进行的货币转换，例如用1美元购买0.5英镑，1英镑可以购买10法郎，一法郎可以购买0.21美元，所以0.5*10*0.21 = 1.05，从中获利百分之五，所以需要编写一个程序，在进行完转换之后能不能获利，如果能就输出Yes，反之No；

样例解释：

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为结束，第一行是一个整数n代表着下面n种货币可以进行转换，再是一个整数m，下面m行代表着m次的转换

思路：用最短路稍微一修改思路即可

 #include <cstdio>

 #include <cstring>

 #include<iostream>

 #include<stdlib.h>

 #include<algorithm>

 using namespace std;

 const int oo = <<;

 const int maxn = ;

 double map[maxn][maxn];

 int n, m,i,j,k,a,b,cnt = ;

 char sh[maxn][maxn];

 char sh1[maxn],sh2[maxn];

 void floyd()

 {

     for(k = ; k < n; k++)

     {

         for(i = ; i < n; i++)

         {

             for(j = ; j < n; j++)

             {

                 if(map[i][k]*map[k][j] > map[i][j])

                 {

                     map[i][j] = map[i][k]*map[k][j];

                 }

             }

         }

     }

     int flag =  ;

     for(i =  ; i < n ; i++)

     {

         if(map[i][i] > 1.0)

         {

             flag =  ;

             break;

         }

     }

     if(flag)

         printf("Case %d: Yes\n",cnt);

     else

         printf("Case %d: No\n",cnt);

 }

 int main()

 {

     double t;

     while(scanf("%d",&n)&&n)

     {

         cnt++;

         memset(map,oo,sizeof(map));

         for(i =  ; i < n ; i++)

         {

             scanf("%s",sh[i]);

             map[i][i] = 1.0 ;

         }

         scanf("%d",&m);

         for(i =  ; i <m ; i++)

         {

             scanf("%s %lf %s",sh1,&t,sh2);

             for(j =  ; j < n ; j++)

             {

                 if(strcmp(sh1,sh[j]) == )

                 {

                     //a = j ;

                     break;

                 }

             }

             for(k =  ; k < n ; k++)

             {

                 if(strcmp(sh2,sh[k]) == )

                 {

                     //b = k ;

                     break ;

                 }

             }

             map[j][k] = t;

         }

         floyd();

     }

     return ;

 }

巴特西

POJ 2240 Arbitrage（floyd）

最新文章

热门文章