MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks

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, 0sizeof(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 

posted on 2008-09-04 14:55 memorygarden 阅读(3395) 评论(4)  编辑 收藏 引用 所属分类: 报告

Feedback

# re: poj 1860 Currency Exchange 2008-09-05 17:36 ziqi
2。 发现d[x] 〉value了,这种时候有可能是图有正环,也有可能图还没有松弛完毕,但是只要发现满足条件,就可以了。
=======================================
如果有正环 结果肯定不对
能过也是因为数据  回复  更多评论
  

# re: poj 1860 Currency Exchange 2008-09-05 20:13 memorygarden
汗。。。。这个题目能增值的一种情况不就是有正环么。。。。这个我在这里 : while(d[x] <= value + eps)//当有正环的时候,总会d[x] > value 的情况,这样就跳出了阿。然后后面返回1,直接就判断yes @ziqi
  回复  更多评论
  

# re: poj 1860 Currency Exchange 2010-06-14 11:31 muye
那如果s点一直不能增值,然后后面又有一个正环在那不断循环,这种情况不会无限循环么??求……@tracer  回复  更多评论
  

# re: poj 1860 Currency Exchange 2012-03-03 20:43 jjyu
e[1001] 是不是可能不够大, 需要 100*99=9900?  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理