求一个回路，从一种货币兑换一圈回到自身，看一路上汇率之积是否大于1

1. //求一个回路，从一种货币兑换一圈回到自身，看一路上汇率之积是否大于1 
2. //扩展常规的最短路bellman,算到dist(n)，就是算到回路 
3. maxdist(k)[v] = max{maxdist(k-1)[v],maxdist(k-1)[u]*C(u,v)} 
4. #include <iostream> 
5. #include <cstring> 
6. #include <cstdio> 
7. #define maxn 50 
8. #define maxm 1000 
9. using namespace std; 
10. struct exchange 
11. { 
12. int ci,cj; 
13. double cij; 
14. }ex[maxm]; 
15. char name[maxn][20],a[20],b[20]; 
16. double x; 
17. int n,m; 
18. double maxdist[maxn]; 
19. int flag; 
20. int kase = 0; 
21. int readcase() 
22. { 
23. scanf("%d",&n); 
24. if(n == 0) 
25. return 0; 
26. for(int i = 0; i < n; i++) 
27. scanf("%s",name[i]); 
28. scanf("%d",&m); 
29. for(int i = 0; i < m; i++) 
30. { 
31. int q,w; 
32. scanf("%s %lf %s",a,&x,b); 
33. for(q = 0; strcmp(a,name[q]);q++) 
34. ; 
35. for(w = 0; strcmp(b,name[w]);w++) 
36. ; 
37. ex[i].ci = q; 
38. ex[i].cj = w; 
39. ex[i].cij = x; 
40. } 
41. return 1; 
42. } 
43. void bellman(int v0) 
44. { 
45. flag = 0; 
46. memset(maxdist,0,sizeof(maxdist)); 
47. maxdist[v0] = 1; 
48. for(int k = 1; k <= n; k++) //1---n 
49. { 
50. for(int i = 0; i < m; i++) 
51. { 
52. if(maxdist[ex[i].ci]*ex[i].cij > maxdist[ex[i].cj]) 
53. maxdist[ex[i].cj] = maxdist[ex[i].ci]*ex[i].cij; 
54. } 
55. } 
56. if(maxdist[v0] > 1.0) 
57. flag = 1; 
58. } 
59. int main() 
60. { 
61. while(readcase()) 
62. { 
63. for(int i = 0; i < n; i++) 
64. { 
65. bellman(i); 
66. if(flag) 
67. break; 
68. } 
69. if(flag) 
70. printf("Case %d: Yes\n",++kase); 
71. else 
72. printf("Case %d: No\n",++kase); 
73. } 
74. } 

本文链接http://www.cxybl.com/html/wyzz/JavaScript_Ajax/20130720/39222.html

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， double
， 自身
， 货币
汇率
一路上有你、一路上有你歌词、一路上有你第二季、一路上有你第一季、一路上有你作文，以便于您获取更多的相关知识。