Bài giải:
Input : Dữ liệu vào từ file PROFIT.INP gồm :
• Dòng đầu tiên gồm 2 số N,M (1<=N<=100) lần lượt là số đảo và số hải trình giữa chúng.
•
M dòng tiếp theo,mỗi dòng gồm 4 số nguyên A,B,C,D (1<=A,B<=N ;
1<=C,D<=255) cho biết tồn tại hải trình giữa hai hòn đảo A,B
trong đó C là số hàng hoá dự kiến sẽ bán được và D là độ dài của hải
trình.
Output : Dữ liệu ra ghi lên file PROFIT.OUT
gồm một số thực P duy nhất là lợi nhuận tối đa ứng với phương án tối ưu
mà bạn tìm được.(Yêu cầu lấy chính xác 3 chữ số sau dấu phẩy).
PROFIT.INP |
PROFIT.OUT |
5 6
1 4 172 100
4 5 184 100
5 1 252 100
1 2 12 100
2 3 10 100
3 1 6 100 |
2.520 |
( Hành trình tương ứng là 1->5->1 )
Thuật giải : Xem
bản đồ vùng biển như là một đồ thị G với N đỉnh và M cung nối trực tiếp
2 chiều. Gọi r là lợi nhuận thu được ứng với một chu trình gồm các cung
L 1 ,L 2 ,…,LN với lượng hàng hoá bán được là T 1 ,T 2 ,….,TN.Xét đồ
thị G(r) với các cung được xây dựng như sau : Di=r*Li-Ti . .Nếu tồn tại
một chu trình âm trên đồ thị G(r) :D 1 +D 2 +…+Dk < 0 ó r*(L 1 +L 2
+…+Lk)-(T 1 +T 2 +…+Tk) < 0 ó r < (T 1 +T 2 +..+Tk)/(L 1 +L 2
+…+Lk) = r 0 ,trong đó r 0 là một phương án thu lợi nhuận khác.Do r
< r 0 nên rõ ràng r chưa phải là phương án tối ưu.Từ đó ta rút ra
nếu r chưa phải tối ưu thì đồ thị G(r) phải chứa chu trình âm.Cũng
tương tự ta có thể dễ dàng chứng minh nếu r lớn hơn giá trị tối ưu thì
G(r) sẽ gồm toàn các chu trình dương (không tồn tại chu trình 0).Như
thế ý tưởng của thuật toán đã khá rõ ràng:phải tìm nhỏ nhất sao cho
G(r) không chứa chu trình âm.Về phương diện cài đặt thì ý tưởng trên
cũng không khó thực hiện,ta chỉ phải tiến hành vét nhị phân r và kiểm
tra việc tồn tại chu trình âm.Để phát hiện chu trình âm thì thông
thường ta nên sử dụng thuật toán Floyd.Độ phức tạp ước tính sẽ là
O(lg(Maxr)*N 3 ) (Maxr là cận trên của r khi vét nhị phân,được xác định
tùy theo mỗi người,miễn là đủ lớn).
Source Code :
{ ------------------------------------------------------------- }
{$M 65521,0,655360}
Const inp='profit.inp';
out='profit.out';
maxn=100;e=0.0001;
oo=1000000000000.0;
Type arr=array[1..maxn] of byte;
data=array[1..maxn] of arr;
Var n,m:integer;
min,max,p,r:real;
t,l:data;
Procedure LoadData;
Var x,y:integer;
Begin
Assign(input,inp);
Reset(input);
Read(n,m);max:=0;
For m:=1 to m do
Begin
Read(x,y,t[x,y],l[x,y]);
t[y,x]:=t[x,y];
l[y,x]:=l[x,y];
max:=max+t[x,y];
End;
Close(input);
End;
Function Negative:boolean;
Var f:array[1..maxn,1..maxn] of real;
i,j,k:integer;
Begin
Negative:=False;
For i:=1 to n-1 do
For j:=i+1 to n do
Begin
If l[i,j]>0 then f[i,j]:=r*l[i,j]-t[i,j]
Else f[i,j]:=oo;
f[j,i]:=f[i,j];
End;
For i:=1 to n do f[i,i]:=oo;
For k:=1 to n do
For i:=1 to n do
For j:=1 to n do
If (f[i,j]<oo) and (f[i,j]>f[i,k]+f[k,j]) then f[i,j]:=f[i,k]+f[k,j];
For k:=1 to n do
For i:=1 to n do
For j:=1 to n do
If (f[i,j]<oo) and (f[i,j]>f[i,k]+f[k,j]) then
Begin
Negative:=True;
exit;
End;
End;
Procedure Solve;
Begin
min:=0;max:=max/m;
Repeat
r:=(min+max)/2;
If Negative then min:=r
Else Begin
p:=r;
max:=r;
End;
Until (max-min)<e;
End;
Procedure Results;
Begin
Assign(output,out);
Rewrite(output);
Writeln(p:0:3);
Close(output);
End;
Begin
LoadData;
Solve;
Results;
End.