POJ 1860 Currency Exchange(最短路 Bellman-Ford)
Currency Exchange 大意：有多种货币，之间可以交换，但是需要手续费，也就是说既有汇率又有手续费。问经过交换之后能不能赚。思路：Bellman_Ford，因为要求最长路，所以松弛条件改一下就好了。
Tips：
3 2 1 20.0
货币的数量 兑换点的数量 主人公拥有的货币量 主人公拥有货币的价值
1 2 1.00 1.00 1.00 1.00
//货币1与货币2交换时，1与2的汇率是1.00,1换2的手续费是1.00,2与1的汇率是1.00,2换1的手续费是1.00。
2 3 1.10 1.00 1.10 1.00
//货币1与货币2交换时，1与2的汇率是1.10,1换2的手续费是1.00,2与1的汇率是1.10,2换1的手续费是1.00。
1 #include <stdio.h>
2 #include <iostream>
3 #include <map>
4 #include <stack>
5 #include <string.h>
6 #define INF 0x3f3f3f3f
7 using namespace std;
8
9 int n, m, s;
10 double v;
11 double dis;
12 int t;
13
14 struct node
15 {
16 int x, y;
17 double r, c;
18 } Map;
19
20 bool Bellman_Ford()
21 {
22 memset(dis, 0, sizeof(dis));
23 dis = v;
24 for(int i = 1; i <= n-1; i++)
25 {
26 bool flag = false;
27 for(int j = 0; j < t; j++)
28 {
29 if(dis.y] < (dis.x]-Map.c)*Map.r)
30 {
31 dis.y] = (dis.x]-Map.c)*Map.r;
32 flag = true;
33 }
34 }
35 if(!flag)
36 {
37 break;
38 }
39 }
40 for(int i = 0; i < t; i++)
41 {
42 if(dis.y] < (dis.x]-Map.c)*Map.r)
43 {
44 return true;
45 }
46 }
47 return false;
48 }
49
50 void Solve()
51 {
52 int a, b;
53 double Rab, Rba, Cab, Cba;
54 while(~scanf("%d%d%d%lf", &n, &m, &s, &v))
55 {
56 t = 0;
57 for(int i = 0; i < m; i++)
58 {
59 scanf("%d%d%lf%lf%lf%lf", &a, &b, &Rab, &Cab, &Rba, &Cba);
60 Map.x = a;
61 Map.y = b;
62 Map.r = Rab;
63 Map.c = Cab;
64 Map.x = b;
65 Map.y = a;
66 Map.r = Rba;
67 Map.c = Cba;
68 }
69 if(Bellman_Ford())
70 {
71 printf("YES\n");
72 }
73 else
74 {
75 printf("NO\n");
76 }
77 }
78 }
79
80 int main()
81 {
82 Solve();
83
84 return 0;
85 }
Currency Exchange
页:
[1]