[POJ1860 Currency Exchange]
[题目来源]：Northeastern Europe 2001, Northern Subregion[关键字]：图论
[题目大意]：套汇问题,汇率为rab,增加一个手续费cab,那么每次套汇的结果是(本金-手续费cab)*汇率rab,现在给出一个人所拥有的货币类型以及拥有该类型货币的总量,需要判断的是经过一系列货币交换后,他能不能是他的货币增值.
//=====================================================================================================
[分析]：其实就是构建出差分约束系统求图中是否存在环。唯一要注意的是由于松弛条件不是一般的加或减，所以松弛不能只作n-1次，而要一直松弛到出现环(d变大)，或不能在松弛。
[代码]：
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 of real;
11 e: array of rec;
12
13 procedure make(x, y: longint; rxy, cxy: real);
14 begin
15 inc(tot);
16 e.x := x;
17 e.y := y;
18 e.cxy := cxy;
19 e.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.y] < (d.x]-e.cxy)*e.rxy then
57 begin
58 d.y] := (d.x]-e.cxy)*e.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]