kuangbin专题专题四 Currency Exchange POJ - 1860

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 #include <string>
 6 #include <vector>
 7 using namespace std;
 8  
 9 typedef long long LL;
10 #define inf (1LL << 30) - 1
11 #define rep(i,j,k) for(int i = (j); i <= (k); i++)
12 #define rep__(i,j,k) for(int i = (j); i < (k); i++)
13 #define per(i,j,k) for(int i = (j); i >= (k); i--)
14 #define per__(i,j,k) for(int i = (j); i > (k); i--)
15 
16 const int N = 110;
17 int n,m,s;
18 double v;
19 int U,V;
20 double Ruv,Cuv,Rvu,Cvu;
21 double value[N];
22 
23 struct node{
24     int u,v;
25     double r,c;
26 };
27 
28 vector<node> E;
29 
30 void input(){
31 
32 
33     rep(i,1,m){
34         cin >> U >> V >> Ruv >> Cuv >> Rvu >> Cvu;
35         E.push_back( node{U,V,Ruv,Cuv} );
36         E.push_back( node{V,U,Rvu,Cvu} );
37     }
38 }
39 
40 bool bellman_ford(){
41 
42     value[s] = v; //其他的货币数额都为0，s的货币金额为V
43 
44     rep(i,2,n){
45         for(int j = 0; j < E.size(); j++){//遍历所有交换情况
46             //如果A->B 能使得B的货币金额变大，就更新
47             if(value[E[j].v] < (value[E[j].u] - E[j].c) * E[j].r){
48                 value[E[j].v] = (value[E[j].u] - E[j].c) * E[j].r;
49             }
50         }
51     }
52 
53     //如果出现A->B 能使得B的货币金额变大，说明有一个正环
54     for(int j = 0; j < E.size(); j++){
55         if(value[E[j].v] < (value[E[j].u] - E[j].c) * E[j].r) return true;
56     }
57     //遍历所有，都没出现正环，说明只有负环
58     return false;
59 }
60 
61 int main(){
62  
63     ios::sync_with_stdio(false);
64     cin.tie(0);
65 
66     cin >> n >> m >> s >> v;
67     input();
68     if (bellman_ford()) cout << "YES" << endl;
69     else cout << "NO" << endl;
70 
71     getchar();getchar();
72     return 0;
73 }