|
试题分析：
此题一看便知是最优化问题。但具体如何解决呢？我们很容易想到用搜索+剪枝的方法，但数据的规模一大，再好的剪枝条件恐怕也无能为力。是否有较高效的算法呢？贪心、动态规划、网络流是解决这类问题的高效算法。但尝试过之后便会发现，前两种算法都无法解决此题。
贪心稍加分析便可找出反例：
1 3
1 5 4
2 3 2
5 3 2
用贪心法找出的解为：0.05（即让第1列火车进站）
而最优解应为：0.06（即让第2、3列火车进站）
而动态规划更是难以下笔，状态的描述、转移、以及是否满足无后效性都很难得到解决。
经过多方面分析：只有用网络流算法才能较好的解决本题。
算法分析：
第一步：建图
①将每一列火车拆成两个点，如第i列火车拆成点i和i'；i到i'之间加一条容量为1，费用为Cost[i]的弧i i'；
②增加一个源点S，S与每个点i连一条容量为1费用为0的弧Si；
③增加一个汇点T，每个点i'与T连一条容量为1费用为0的弧i'T；
④对于所有的i和j（i≠j，且i，j∈1..m）,如果Reach[i]+Stay[i]<
Reach[j]，则在i'与j之间连一条容量为1，费用为0弧；
对于上面这个图，求一个流量不超过n得最大费用最大流，如果ii'的流量为1，则让第i列火车进站。
第二步：求图的最大费用最大流
说明:
用i+m表示i'（i∈1..m），用2 * m + 1表示S，用2 * m + 2表示T。
c[i，j]表示i到j的容量（i，j∈1..2*m+2）
f[i，j]表示i到j的流量（i，j∈1..2*m+2）
v[i，j]表示i到j的费用（i，j∈1..2*m+2）
具体步骤：
反复执行n次如下过程：
1、 计算从S到T的最长路：
①赋权值：
f[i，j] < c[i，j] :w[i,j] := v[i,j]；
f[i，j] > 0 :w[i,j] := -v[i,j]；
i，j∈1..2*m+2
②以w[i，j]为权值求从S到T的最长路
2、 如果存在最长路则以1为可改进量，一最长路径为增广轨，对f数租进行改进，否则结束；
第三步：输出
源程序：
{$A-,S-,X-,Y-}
program Train;
const
Fn1 = 'Train.In';
Fn2 = 'Train.Out';
MaxN = 20;
MaxM = 100;
Max = MaxM SHL 1 + 1 + 1;
Min = - MaxLongint;
type
PathType = record
From: Integer;
Cost: Longint
{Cost[I]，从原点到达I得最长路径的长度}
end;
var
N, M, S, T: Byte;
{S：原点}{T：汇点}
Answer: Longint;
Cost: array[1 .. Max] of Longint;
ReachTime, StayTime: array[1 .. MaxM] of Integer;
Path: array[1 .. Max] of PathType;
G: array[1 .. Max, 1 .. Max] of Byte;
{G[I，j]=0:容量为0
{G[I，j]=1:容量为1，流量为0}
{G[I，j]=2:容量为1，流量为1}
procedure Init;{输入}
var
i: Byte;
begin
Assign(Input, Fn1);
Reset(Input);
Readln(N, M);
for i := 1 to M do Readln(ReachTime[i], Cost[i], StayTime[i]);
Close(Input)
end;
procedure GetReady;
var
i, j: Byte;
Leave: Integer;{出站时间}
begin
T := M SHL 1 + 1;
S := M SHL 1 + 2;
for i := 1 to M do
begin
G[S, i] := 1;
G[i, i + M] := 1;
G[i + M, T] := 1;
Leave := ReachTime[i] + StayTime[i];
for j := 1 to M do
if Leave < ReachTime[j] then G[i + M, j]:=1
end
end;
procedure FindLongestWay;{寻找最长路}
var
i, j: Integer;
X: Longint;
CouldQuit: Boolean;
begin
for i := 1 to T do Path[i].Cost := Min;
repeat
CouldQuit := True;
for i := 1 to S do
if Path[i].Cost > Min then
for j := 1 to T do
if G[i, j] = 1 then
begin
X := Path[i].Cost;
if (j < T) and (j - i = M) then Inc(X, Cost[i]);
if X > Path[j].Cost then
begin
Path[j].From := i;
Path[j].Cost := X;
CouldQuit := False
end
end else
if G[j, i] = 2 then
begin
X := Path[i].Cost;
if (i < T) and (i - j = M) then Dec(X, Cost[j]);
if X > Path[j].Cost then
begin
Path[j].From := -i;
Path[j].Cost := X;
CouldQuit := False
end
end
until CouldQuit
end;
procedure Work;{根据可改进路修改流量}
var
i, j: Integer;
begin
j := T;
i := Path[T].From;
repeat
if i > 0 then Inc(G[i, j])
else Dec(G[j, -i]);
j := Abs(i);
i := Path[j].From
until i = 0
end;
procedure Main;
var
i: Byte;
begin
GetReady;
for i := 1 to N do
begin
FindLongestWay;
if Path[T].From <= 0 then Exit;
{找不到可改进路，或最长路径<=0，则退出}
Work
end
end;
procedure Print;
var
i: Byte;
begin
for i := 1 to M do
if G[i, i + M] = 2 then Inc(Answer, Cost[i]);
Assign(Output, Fn2);
Rewrite(Output);
Writeln(Answer / 100: 0: 2);
Close(Output)
end;
begin
Init;
Main;
Print
end.
|
