题目链接：https://vjudge.net/problem/POJ-1860
大致题意：有不同的货币，有很多货币交换点，每个货币交换点只能两种货币相互交换，有佣金C，汇率R。
每次交换算一次操作，问能不能经过一系列操作使得本来的货币的本金数额变大。
思路：相当于图，“一系列操作使得本金数额变大”说明有一个正的回路，能使得某种货币的数额增大，那么，
只要有这一个正的回路，那么我们一定可以让某种货币的数额变为无穷大，那么本来的货币的本金数额变大是一定的，
所有，我们只需要判断图中是否出现了一个正回路，有的话说明可以，一个没有说明都是负环，说明不能。
（这里有一个误区，只判断一次货币交换情况及就判断，可能A货币换成B货币的佣金很大或者汇率很低，那么只要我们有一个正环，
使得B的货币数额变为正无穷大，那么经过一系列操作后最后A的货币数额一定是增大的）
有负环，这里用bellman_ford算法也可以通过。
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 bool flag = true; 45 rep(i,2,n){ 46 flag = false;//每次赋值false，检测下面循环还能不能进行更新操作 47 for(int j = 0; j < E.size(); j++){//遍历所有交换情况 48 //如果A->B 能使得B的货币金额变大，就更新 49 if(value[E[j].v] < (value[E[j].u] - E[j].c) * E[j].r){ 50 value[E[j].v] = (value[E[j].u] - E[j].c) * E[j].r; 51 } 52 53 flag = true;//进行了更新操作 54 } 55 if(!flag) break;//无法再进行更新操作 56 } 57 58 //如果出现A->B 能使得B的货币金额变大，说明有一个正环 59 for(int j = 0; j < E.size(); j++){ 60 if(value[E[j].v] < (value[E[j].u] - E[j].c) * E[j].r) return true; 61 } 62 //遍历所有，都没出现正环，说明只有负环 63 return false; 64 } 65 66 int main(){ 67 68 ios::sync_with_stdio(false); 69 cin.tie(0); 70 71 cin >> n >> m >> s >> v; 72 input(); 73 if (bellman_ford()) cout << "YES" << endl; 74 else cout << "NO" << endl; 75 76 getchar();getchar(); 77 return 0; 78 }