POJ 1860 Currency Exchange

知识点: 判断正环

题目地址 | Here

题意

我们的城市有M个货币兑换点,N种货币。让我们假设每一个点都只能兑换专门的两种货币。可以有几个点,专门从事相同货币兑换。
例如,如果你想换100美元到俄罗斯卢布兑换点,那里的汇率是29.75,而佣金是0.39,你会得到(100 - 0.39)×29.75=2963.3975卢布。

问: nick有VS国的货币,他希望能通过一些操作(在不同的兑换点兑换),增加他的资本。当然,他想在最后手中的钱仍然是S国的。帮他解答这个难题,看他能不能完成这个愿望。

输入

!!! 单组输入 !!!

先输入N(钟货币)、M(个兑换点)、S(当前持有货币类型)、V(持有金额)
然后输入M行,每行输入5个数字分别为:

1
a国货币   b国货币   从a->b的佣金    从a->b的手续费  从b->a的佣金    从b->a的手续费

1
2
3
3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00

输出

假设钱可以变多,就输出YES,否则输出NO

1
YES

题解

其实只要在图中找一个环,这个环可以使得金额变多即可。因为有了’正’环,就可增长到无限多,兑换回原来的货币就不用考虑,亏损了。

至于如何判断是否存在一个’正’环?用bellmanford来判断即可,虽然之前是求最短路,但是改变松弛条件后,遇到正环也会无限循环,即超过最大松弛次数 $n-1$次,即存在’正’环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <algorithm>
#include <stdio.h>
#include <queue>
using namespace std;

const int maxn = 120;
float d[maxn];
int head[maxn],ct[maxn];
bool vis[maxn];
struct Edge {
int to,nxt;
//r是汇率,c是佣金
float r,c;
void def(float _r,float _c) { r=_r,c=_c; }
} e[maxn<<4];
int cnt;
void init(int n) {
for(int i=0; i<=n; i++) head[i]=-1;
}
void addEdge(int a,int b,float r,float c) {
cnt++;
e[cnt].to=b; e[cnt].nxt=head[a]; e[cnt].def(r,c);
head[a]=cnt;
}
int spfa(int s,int n) {
int now;
float tmp,old=d[s];
queue<int> list;
list.push(s);
while(!list.empty()) {
now = list.front();
list.pop();
vis[now]=0;
for(int i=head[now]; i!=-1; i=e[i].nxt) {
if((!vis[e[i].to]&&(tmp=(d[now]-e[i].c)*e[i].r)>d[e[i].to])) {
d[e[i].to]=tmp;
vis[e[i].to]=1;
ct[e[i].to]++; //判断正环的部分
list.push(e[i].to);
if(ct[e[i].to]>=n) return 1;
}
}
}
return 0;
}

int main() {
int a,b;
int n,m,s;
float v;
float rab,rba;
float cab,cba;
scanf("%d%d%d%f",&n,&m,&s,&v);
init(n);
d[s]=v;
while(m--) {
scanf("%d%d%f%f%f%f",&a,&b,&rab,&cab,&rba,&cba);
addEdge(a,b,rab,cab);
addEdge(b,a,rba,cba);
}
printf("%s\n",spfa(s,n)?"YES":"NO");
return 0;
}


--------------------------END--------------------------
喜欢的话,不妨请我喝杯奶茶(≧∇≦)ノ