hdu 1217 Arbitrage（佛洛依德）

Arbitrage

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6360 Accepted Submission(s): 2939

Problem Description

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.

Input

The input file 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.

Output

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

Sample Input

USDollar

BritishPound

FrenchFranc

USDollar 0.5 BritishPound

BritishPound 10.0 FrenchFranc

FrenchFranc 0.21 USDollar

USDollar

BritishPound

FrenchFranc

USDollar 0.5 BritishPound

USDollar 4.9 FrenchFranc

BritishPound 10.0 FrenchFranc

BritishPound 1.99 USDollar

FrenchFranc 0.09 BritishPound

FrenchFranc 0.19 USDollar

Sample Output

Case 1: Yes

Case 2: No

Source

University of Ulm Local Contest 1996

Recommend

Eddy | We have carefully selected several similar problems for you: 1142 1162 1385 1301 1596

最短路的变形，由于数据只到30，所以可以采用floyd算法，不过需要注意的是，这里是求最大的倍率。

题意：题目大意就是给了你各种货币之间的兑换关系，问你是否存在1个单元的某货币经过一个回路的兑换后>=1个单元( 有利润 )。

附上代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #define M 35
 6 using namespace std;
 7 double map[M][M];
 8 int n;
 9 
10 void floyd()  //利用floyd算法计算最大赔率
11 {
12     int k,i,j;
13     for(k=1; k<=n; k++)
14         for(i=1; i<=n; i++)
15             for(j=1; j<=n; j++)
16                 if(map[i][j]<map[i][k]*map[k][j])
17                     map[i][j]=map[i][k]*map[k][j];
18 }
19 
20 int main()
21 {
22     int m,i,j,w=1;
23     char s[M],str[M][M];
24     while(~scanf("%d",&n)&&n)
25     {
26         for(i=1; i<=n; i++)
27             scanf("%s",str[i]);
28         for(i=1; i<=n; i++)
29             for(j=1; j<=n; j++)
30             {
31                 if(i==j) map[i][j]=1;  //因为是找最大的汇率，因此初始时本身转本身为1，其他转化为0
32                 else     map[i][j]=0;
33             }
34         scanf("%d",&m);
35         int a,b;
36         double c;
37         for(i=1; i<=m; i++)
38         {
39             scanf("%s",s);
40             for(a=1; a<=n; a++)    //将其转化为map数组记录
41                 if(!strcmp(s,str[a]))
42                     break;
43             scanf("%lf",&c);
44             scanf("%s",s);
45             for(b=1; b<=n; b++)
46                 if(!strcmp(s,str[b]))
47                     break;
48             map[a][b]=c;
49         }
50         floyd();
51         cout<<"Case "<<w++<<": ";
52         if(map[1][1]>1)
53             cout<<"Yes"<<endl;
54         else
55             cout<<"No"<<endl;
56     }
57     return 0;
58 }

邻接表：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <queue>
  5 #define N 35
  6 #define M 35*35*10
  7 #define INF 0x3f3f3f3f
  8 using namespace std;
  9 struct Edge
 10 {
 11     int from,to;
 12     double val;
 13     int next;
 14 } edge[M*2];
 15 int n,m,tol,s,t,fail;
 16 double dis[N];
 17 bool vis[N];
 18 int head[M*2];
 19 
 20 void init()
 21 {
 22     tol=0;
 23     memset(head,-1,sizeof(head));
 24 }
 25 
 26 void addEdge(int u,int v,double w)
 27 {
 28     edge[tol].from=u;
 29     edge[tol].to=v;
 30     edge[tol].val=w;
 31     edge[tol].next=head[u];
 32     head[u]=tol++;
 33 }
 34 
 35 
 36 void getmap()
 37 {
 38     char str[N][N];
 39     char s[N];
 40     for(int i=1; i<=n; i++)
 41         scanf("%s",str[i]);
 42     int a,b;
 43     double c;
 44     scanf("%d",&m);
 45     while(m--)
 46     {
 47         scanf("%s",s);
 48         for(a=1; a<=n; a++)
 49             if(!strcmp(s,str[a]))
 50                 break;
 51         scanf("%lf",&c);
 52         scanf("%s",s);
 53         for(b=1; b<=n; b++)
 54             if(!strcmp(s,str[b]))
 55                 break;
 56         addEdge(a,b,c);
 57     }
 58     memset(vis,false,sizeof(vis));
 59     memset(dis,0,sizeof(dis));
 60 }
 61 
 62 void spfa()
 63 {
 64     queue<int>q;
 65     q.push(1);
 66     dis[1]=1.0;
 67     vis[1]=true;
 68     while(!q.empty())
 69     {
 70         int u=q.front();
 71         q.pop();
 72         vis[u]=false;
 73         for(int i=head[u]; i!=-1; i=edge[i].next)
 74         {
 75             int v=edge[i].to;
 76             if(dis[v]<dis[u]*edge[i].val)
 77             {
 78                 dis[v]=dis[u]*edge[i].val;
 79                 if(!vis[v])
 80                 {
 81                     vis[v]=true;
 82                     q.push(v);
 83                 }
 84                 if(dis[1]>1)
 85                 {
 86                     fail=1;
 87                     return;
 88                 }
 89 
 90             }
 91         }
 92     }
 93 
 94 
 95 }
 96 
 97 int main()
 98 {
 99 
100     int i,j,T=1;
101     while(~scanf("%d",&n)&&n)
102     {
103         init();
104         getmap();
105         printf("Case %d: ",T++);
106         fail=0;
107         spfa();
108         if(fail)
109             printf("Yes
");
110         else
111             printf("No
");
112     }
113     return 0;
114 }