HDU 1217 Arbitrage题意是说给你N种货币以及,货币与货币之间的M种汇率,
让你判断是否存在经过若干次货币的兑换使得某种货币的
价值大于原来本身的价值,比如所:美元:美元 = 1 : 1;
题意就是让你判断,在当前的货币兑换率的基础上,能不能
使 美元 : 美元 > 1 : 1; 利用Floyd算法即可搞定,代码如下:
1 #include<iostream>
2 #include<queue>
3 #include<cstring>
4 #define size 40
5 #define inf 0
6 using namespace std;
7 char s1[100],s2[100],str[40][100];
8 double map[size][size], dir[size], x;
9 int n, m, k, a, b, flag = 1;
10
11 int tree(char s[])
12 {
13 for(int a=0;a<n;a++)
14 if(strcmp(s,str[a])==0)return a;
15 }
16
17 int main()
18 {
19 while(scanf("%d", &n), n)
20 {
21 int c,d,e;
22 k=0;
23 for(a=0;a<n;a++)
24 {
25 scanf("%s", &str[a]);
26 }
27 scanf("%d", &m);
28 for(a=0;a<size;a++)
29 for(b=0;b<size;b++)
30 map[a][b]=0;
31 while(m--)
32 {
33 scanf("%s %lf %s", &s1, &x, &s2);
34 a=tree(s1);
35 b=tree(s2);
36 map[a][b]=x;
37 }
38 for(c=0;c<n;c++)
39 for(d=0;d<n;d++)
40 for(e=0;e<n;e++)
41 if(map[d][c]*map[c][e]>map[d][e])
42 {
43 map[d][e]=map[d][c]*map[c][e];
44 if(map[0][0]>1)break;
45 }
46 if(map[0][0]>1)
47 cout<<"Case "<<flag<<": Yes"<<endl;
48 else
49 cout<<"Case "<<flag<<": No"<<endl;
50 flag++;
51 }
52 }