设为首页 收藏本站
查看: 984|回复: 0

[经验分享] [POJ1860 Currency Exchange]

[复制链接]

尚未签到

发表于 2015-9-12 07:10:12 | 显示全部楼层 |阅读模式
  [题目来源]:Northeastern Europe 2001, Northern Subregion
  [关键字]:图论
  [题目大意]:套汇问题,汇率为rab,增加一个手续费cab,那么每次套汇的结果是(本金-手续费cab)*汇率rab,现在给出一个人所拥有的货币类型以及拥有该类型货币的总量,需要判断的是经过一系列货币交换后,他能不能是他的货币增值.
  //=====================================================================================================
  [分析]:其实就是构建出差分约束系统求图中是否存在环。唯一要注意的是由于松弛条件不是一般的加或减,所以松弛不能只作n-1次,而要一直松弛到出现环(d[st]变大),或不能在松弛。
  [代码]:


DSC0000.gif DSC0001.gif View Code


1 program Project1;
2 type
3   rec = record
4     x, y: longint;
5     cxy, rxy: real;
6   end;
7 var
8   n, m, s, tot: longint;
9   ds: real;
10   d: array[0..1000] of real;
11   e: array[0..2000] of rec;
12
13 procedure make(x, y: longint; rxy, cxy: real);
14 begin
15   inc(tot);
16   e[tot].x := x;
17   e[tot].y := y;
18   e[tot].cxy := cxy;
19   e[tot].rxy := rxy;
20 end;
21
22 procedure init;
23 var
24   i, x, y: longint;
25   rxy, cxy, ryx, cyx: real;
26 begin
27   readln(n,m,s,ds);
28   for i := 1 to n do d := -9999999;
29   d := ds;
30   for i := 1 to m do
31     begin
32       readln(x,y,rxy,cxy,ryx,cyx);
33       make(x,y,rxy,cxy);
34       make(y,x,ryx,cyx);
35     end;
36 end;
37
38 procedure print(x: longint);
39 begin
40   if x = 1 then writeln('YES');
41   if x = 0 then writeln('NO');
42   //readln;
43   //readln;
44   halt;
45 end;
46
47 procedure bellman;
48 var
49   i, j: longint;
50   f: boolean;
51 begin
52   while 1 = 1 do
53     begin
54       f := true;
55       for j := 1 to tot do
56         if d[e[j].y] < (d[e[j].x]-e[j].cxy)*e[j].rxy then
57           begin
58             d[e[j].y] := (d[e[j].x]-e[j].cxy)*e[j].rxy;
59             f := false;
60           end;
61        if d > ds then print(1);
62        if f then print(0);
63     end;
64 end;
65
66 begin
67   init;
68   bellman
69 end.
  

运维网声明 1、欢迎大家加入本站运维交流群:群②:261659950 群⑤:202807635 群⑦870801961 群⑧679858003
2、本站所有主题由该帖子作者发表,该帖子作者与运维网享有帖子相关版权
3、所有作品的著作权均归原作者享有,请您和我们一样尊重他人的著作权等合法权益。如果您对作品感到满意,请购买正版
4、禁止制作、复制、发布和传播具有反动、淫秽、色情、暴力、凶杀等内容的信息,一经发现立即删除。若您因此触犯法律,一切后果自负,我们对此不承担任何责任
5、所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其内容的准确性、可靠性、正当性、安全性、合法性等负责,亦不承担任何法律责任
6、所有作品仅供您个人学习、研究或欣赏,不得用于商业或者其他用途,否则,一切后果均由您自己承担,我们对此不承担任何法律责任
7、如涉及侵犯版权等问题,请您及时通知我们,我们将立即采取措施予以解决
8、联系人Email:admin@iyunv.com 网址:www.yunweiku.com

所有资源均系网友上传或者通过网络收集,我们仅提供一个展示、介绍、观摩学习的平台,我们不对其承担任何法律责任,如涉及侵犯版权等问题,请您及时通知我们,我们将立即处理,联系人Email:kefu@iyunv.com,QQ:1061981298 本贴地址:https://www.yunweiku.com/thread-112425-1-1.html 上篇帖子: Windows 2008下部署Exchange Server 2007 下篇帖子: 如何解决 Exchange Server 2003 传输问题
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

扫码加入运维网微信交流群X

扫码加入运维网微信交流群

扫描二维码加入运维网微信交流群,最新一手资源尽在官方微信交流群!快快加入我们吧...

扫描微信二维码查看详情

客服E-mail:kefu@iyunv.com 客服QQ:1061981298


QQ群⑦:运维网交流群⑦ QQ群⑧:运维网交流群⑧ k8s群:运维网kubernetes交流群


提醒:禁止发布任何违反国家法律、法规的言论与图片等内容;本站内容均来自个人观点与网络等信息,非本站认同之观点.


本站大部分资源是网友从网上搜集分享而来,其版权均归原作者及其网站所有,我们尊重他人的合法权益,如有内容侵犯您的合法权益,请及时与我们联系进行核实删除!



合作伙伴: 青云cloud

快速回复 返回顶部 返回列表