TOJ 1745 Arbitrage floyd

叁歲伎倆 2022-05-18 02:16 137阅读 0赞

**1745: Arbitrage**

**描述**

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 \* 10.0 \* 0.21 = 1.05 US dollars, making a profit of 5 percent.  
  
Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.

**输入**

The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. 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.  
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.

**输出**

For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".

**样例输入**

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

**样例输出**

Case 1: Yes  
Case 2: No

货币转化问题，先给出n种货币的名称，然后给出m种转化关系，可以以关系建图，问是否可以从转化中获利，用floyd判断一下乘积即可。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    int main()
    {
    	map<string,int>name;
    	string s,s2;
    	double a[50][50],r;
    	int n,m,i,j,k,o=1;
     	while(scanf("%d",&n))
        {
        	if(n==0)break;
            for(i=1;i<=n;i++)
            {
                cin>>s;
                name[s]=i;
            } 
            for(i=1;i<=n;i++)
               for(j=1;j<=n;j++)
               {
                   if(i==j)
    			   a[i][j]=1;
                   else 
    			   a[i][j]=0;
               } 
    	    scanf("%d",&m);   
            while(m--)
            {
                cin>>s;
                cin>>r;
                cin>>s2;
                a[name[s]][name[s2]]=r;
            }        
            for(k=1;k<=n;k++)
    		{
    		    for(i=1;i<=n;i++)
    		    {
    		        for(j=1;j<=n;j++)
    		        {
    		            if(a[i][j]<a[i][k]*a[k][j])
    		            {
    		                a[i][j]=a[i][k]*a[k][j];
    		            }
    		        }
    		    }
    		}	
    		bool flag=false;
            for(i=1;i<=n;i++)
            {
            	if(a[i][i]>1)
              	{
    				flag=true;
    				break;
      			}
            }
            if(flag)  
    		printf("Case %d: Yes\n",o++);
            else 
    		printf("Case %d: No\n",o++);      
        }
    }