最短路(Bellman_Ford) POJ 1860 Currency Exchange
题目传送门
1 /*
2 最短路(Bellman_Ford)：求负环的思路，但是反过来用，即找正环
3 详细解释：http://blog.iyunv.com/lyy289065406/article/details/6645778
4 */
5 #include <cstdio>
6 #include <iostream>
7 #include <algorithm>
8 #include <cstring>
9 #include <vector>
10 #include <cmath>
11 #include <queue>
12 #include <map>
13 #include <set>
14 using namespace std;
15
16 const int MAXN = 100 + 10;
17 const int INF = 0x3f3f3f3f;
18 const double EPS = 1e-8;
19 struct NODE
20 {
21 int u, v;
22 double r, c;
23 }node;
24 double d;
25
26 bool Bellman_Ford(int s, int n, int tot, double V)
27 {
28 memset (d, 0, sizeof (d));
29 d = V;
30 bool flag;
31 for (int i=1; i<=n-1; ++i)
32 {
33 flag = false;
34 for (int j=1; j<=tot; ++j)
35 {
36 NODE e = node;
37 if (d < (d - e.c) * e.r)
38 {
39 d = (d - e.c) * e.r; flag = true;
40 }
41 }
42 if (!flag) break;
43 }
44
45 for (int i=1; i<=tot; ++i)
46 {
47 NODE e = node;
48 if (d < (d - e.c) * e.r) return true;
49 }
50
51 return false;
52 }
53
54 int main(void) //POJ 1860 Currency Exchange
55 {
56 //freopen ("A.in", "r", stdin);
57
58 int n, m, s;
59 double V;
60 while (~scanf ("%d%d%d%lf", &n, &m, &s, &V))
61 {
62 int tot = 0;
63 for (int i=1; i<=m; ++i)
64 {
65 int x, y;
66 double rab, cab, rba, cba;
67 scanf ("%d%d%lf%lf%lf%lf", &x, &y, &rab, &cab, &rba, &cba);
68 //printf ("%d %d %lf %lf %lf %lf\n", x, y, rab, cab, rba, cba);
69 node[++tot].u = x; node.v = y;
70 node.r = rab; node.c = cab;
71 node[++tot].u = y; node.v = x;
72 node.r = rba; node.c = cba;
73 }
74
75 if (Bellman_Ford (s, n, tot, V)) puts ("YES");
76 else puts ("NO");
77 }
78
79 return 0;
80 }
页:
[1]