HDU 1217 Arbitrage

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 }


posted on 2011-08-17 09:55 AK 阅读(1529) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

资源连接

搜索

最新评论

阅读排行榜

评论排行榜