测评机: Xeost[5]
得分: 0分
提交日期: 2012-8-5 18:00:00
有效耗时: 该状态没有记录
测试结果1: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果2: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果3: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果4: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果5: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果6: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果7: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果8: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果9: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
测试结果10: 输出过长|用户输出数据超过标准输出两倍[标准输出0位|选手输出4位]
program rq570;
const mo=20005;
type
point=^nod;
nod=record
next,opp:point;
t,fee,cap:longint;
end;
var
node:array[0..20001] of point;
n,m,k:integer;
d,loc:array[1..100,1..100] of longint;
q:array[1..20005] of longint;
flag:array[0..20001] of boolean;
dis:array[0..20001] of longint;
prev:array[0..20001] of integer;
preva:array[0..20001] of point;
h,t:longint;
tt,ss,pp,z:longint;
procedure build_arc(s,t,cap,fee:longint);
var p,q:point;
begin
new(p);
p^.fee:=-fee;
p^.cap:=cap;
p^.t:=t;
p^.next:=node[s];
node[s]:=p;
q:=p;
new(p);
p^.fee:=fee;
p^.cap:=0;
p^.t:=s;
p^.next:=node[t];
node[t]:=p;
p^.opp:=q;
q^.opp:=p;
end;
procedure init;
var i,j:integer;
begin
ss:=0;
readln(k,m,n);
for i:=1 to n do
for j:=1 to m do read(d[i][j]);
for i:=0 to 2*m*n+1 do node[i]:=nil;
end;
procedure build_graph;
var i,j:integer;
begin
tt:=2*m*n+1;
pp:=0;
for i:=n downto 1 do
for j:=m downto 1 do
begin
build_arc(pp+1,pp+2,1,d[i][j]);
build_arc(pp+1,pp+2,k,0);
if i<>n then build_arc(pp+2,loc[i+1][j],k,0);
if j<>m then build_arc(pp+2,loc[i][j+1],k,0);
loc[i][j]:=pp+1;
inc(pp,2);
end;
build_arc(0,loc[1][1],k,0);
build_arc(loc[n][m]+1,tt,k,0);
end;
procedure spfa_work;
var i,j:integer;
tmp,r:integer;
min:longint;
p:point;
begin
z:=0;
for i:=1 to k do
begin
fillchar(flag,sizeof(flag),false);
for j:=1 to tt do dis[j]:=maxlongint;
h:=0;t:=1;
q[1]:=0;
flag[0]:=true;
dis[0]:=0;
while h<>t do
begin
h:=(h mod mo)+1;
p:=node[q[h]];
while p<>nil do
begin
tmp:=p^.t;
if (p^.cap>0)and(dis[q[h]]+p^.fee<dis[tmp]) then
begin
dis[tmp]:=dis[q[h]]+p^.fee;
prev[tmp]:=q[h];
preva[tmp]:=p;
if not flag[tmp] then
begin
t:=(t mod mo)+1;
q[t]:=tmp;
flag[tmp]:=true;
end;
end;
p:=p^.next;
end;
flag[q[h]]:=false;
end;
inc(z,dis[tt]);
r:=tt;
while r<>0 do
begin
dec(preva[r]^.cap);
inc(preva[r]^.opp^.cap);
r:=prev[r];
end;
end;
writeln(-z);
end;
begin
init;
build_graph;
spfa_work;
end.