[poj1860] Currency Exchange (bellman-ford算法)

yxxs123

　　题目链接：http://poj.org/problem?id=1860
　　题目大意：给你一些兑换方式，问你能否通过换钱来赚钱？
　　
　　使用ford算法，当出现赚钱的时候就返回YES，如果不能赚钱，则返回NO
　　应该是可以停下来的，但是我不会分析复杂度，谁来教教我？
　　
　　



1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <vector>
5 #include <map>
6 #include <set>
7 #include <bitset>
8 #include <cmath>
9 #include <numeric>
10 #include <iterator>
11 #include <iostream>
12 #include <cstdlib>
13 using namespace std;
14 #define PB push_back
15 #define MP make_pair
16 #define SZ size()
17 #define ST begin()
18 #define ED end()
19 #define CLR clear()
20 #define ZERO(x) memset((x),0,sizeof(x))
21 typedef long long LL;
22 typedef unsigned long long ULL;
23 typedef pair<int,int> PII;
24 const double EPS = 1e-8;
25
26 struct EDGE{
27     int from,to;
28     double r,c;
29     EDGE(int _from = 0, int _to =0 , double _r = 0, double _c = 0 ) :
30         from(_from),to(_to),r(_r),c(_c) {}
31 };
32
33 vector<EDGE> vec;
34 int N,M,S;
35 double V;
36 double d[111];
37
38 bool floyd(int s){
39     d = V;
40     bool flag = false;
41     while(true){
42         flag = false;
43         for(int i=0;i<vec.SZ;i++){
44             const EDGE& e = vec;
45             if(d[e.from]>0.0 && d[e.to]<(d[e.from]-e.c)*e.r){
46                 d[e.to]=(d[e.from]-e.c)*e.r;
47                 flag = true;
48             }
49         }
50         if(d>V) return true;
51         if(!flag) {
52             break;
53         }
54     }
55     return d>V;
56 }
57
58
59 int main(){
60     while(EOF!=scanf("%d%d%d%lf",&N,&M,&S,&V)){
61         vec.CLR;
62         ZERO(d);
63         int from,to;
64         double rab,cab,rba,cba;
65         for(int i=0;i<M;i++){
66             scanf("%d%d%lf%lf%lf%lf",&from,&to,&rab,&cab,&rba,&cba);
67             vec.PB(EDGE(from,to,rab,cab));
68             vec.PB(EDGE(to,from,rba,cba));
69         }
70         puts(floyd(S)?"YES":"NO");
71     }
72     return 0;
73 }