http://acm.pku.edu.cn/JudgeOnline/problem?id=1860
感谢aowarmen 指出我的错误
题意 : 就是套汇的问题,汇率Rab, 增加了一个手续费 Cab 。。。。。。。每次的结果是 (本金 - 手续费) * 汇率,而且一个人拥有的钱的类型是已知的,拥有的value 钱的个数也是已知的, 问你能不能增值。
输入 :
3 2 1 20.0 //钱种类个数 汇率的个数,拥有第几种钱, 拥有多少钱
1 2 1.00 1.00 1.00 1.00 //钱a, 钱b, rab, cab, rba, cba
2 3 1.10 1.00 1.10 1.00
想法: 应用bellman-ford :
应用bellman求解最短路径(上界松弛)和最长路径(下界松弛)的时候,都是松弛 点 - 1 次, 然后再看能否再进行松弛了。如果能,就证明有环。否则为最短或者最长路径(希望错了请大家指出)
当时看这个题的时候,被bellman求解最短路给束缚了, 即循环是 点 - 1 次, 但是这种最长路的正环不一定就在 点 - 1 次松弛后,就能让目标点符合要求,也即是说不一定能松弛连接目标点的边,因为要看d[u]与d[目标点(v)]的关系,也就是边,就像最短路得负环一样,他们是无限的增长下去的。
所以这个题 循环的终止条件有2个 :
1。 当不能松弛的时候停止, 这样就代表这个图中没有正环,这样判断一下d[x]是否大于value就可以了。
2。 发现d[x] 〉value了,这种时候有可能是图有正环,也有可能图还没有松弛完毕,但是只要发现满足条件,就可以了。
对了,这个题还要注意精度
代码如下:
1 #include <stdio.h>
2 #include <string.h>
3 #define eps 1e-8
4 using namespace std;
5 int m, n, x, el;double value;
6 struct E{
7 int u, v;
8 double r, c;
9 }e[1001];
10 bool bellman(){
11 int i, j, f, p[102], u, v;double r, c, d[102];
12 memset(d, 0, sizeof(d));
13 d[x] = value;
14 while(d[x] <= value + eps){
15 f = 0;
16 for(j = 0; j <= el; j++){
17 if(d[e[j].v] + eps < (d[e[j].u] - e[j].c) * e[j].r ){
18 d[e[j].v] = (d[e[j].u] - e[j].c) * e[j].r;
19 p[e[j].v] = e[j].u;
20 f = 1;
21 }
22 }
23 if(!f)
24 return d[x] > value + eps;
25 }
26 return 1;
27 }
28 int main(){
29 freopen("1860.in","r",stdin);
30 freopen("1860.out","w",stdout);
31 int i, j, u, v, f;double ruv, cuv, rvu, cvu;
32 while(scanf("%d%d%d%lf", &m, &n, &x, &value) != -1){
33 el = 0;
34 for(i = 0; i < n; i++){
35 scanf("%d%d%lf%lf%lf%lf", &u, &v, &ruv, &cuv, &rvu, &cvu);
36 e[el].u = u;
37 e[el].v = v;
38 e[el].r = ruv;
39 e[el++].c = cuv;
40 e[el].u = v;
41 e[el].v = u;
42 e[el].r = rvu;
43 e[el++].c = cvu;
44 }
45 if(bellman())puts("YES");
46 else puts("NO");
47 }
48 return 0;
49 }
50
51