kuangbin专题专题四 Currency Exchange POJ - 1860

发布时间：2020-12-14 04:40:53 所属栏目：大数据来源：网络整理

导读：? 题目链接：https://vjudge.net/problem/POJ-1860 大致题意：有不同的货币，有很多货币交换点，每个货币交换点只能两种货币相互交换，有佣金C，汇率R。每次交换算一次操作，问能不能经过一系列操作使得本来的货币的本金数额变大。思路：相当于图，“一

?

题目链接：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,k) for(int i = (j); i < (k); i++)
13 #define per(i,k) for(int i = (j); i >= (k); i--)
14 #define per__(i,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,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 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!