算法正确(费用流)
和ByVoid标程对拍 无错
错误都是
某一行标准输出为 0/1
选手输出为 一个更大的整数
eg
标准输出 0
选手输出 141
代码
program rq459;
type pnode=longint;
tnode=record
n,c,w,f:longint;
next:pnode;
end;
const maxn=3217;
maxint=longint($3f3f3f3f);
var mem:array[1..790117] of tnode;
g:array[1..maxn] of pnode;
v:array[1..maxn] of boolean;
hori,vert,ans:array[1..47,1..47] of longint;
n,m,cost,flow,size,st,trm,dist,row,col,tot:longint;
inf,ouf:array[1..maxn] of longint;
function min(a,b:longint):longint; begin
if a<b then exit(a) else exit(b); end;
procedure insnbs(u,v,ic,iw:longint);
begin
inc(size);
with mem[size] do begin
n:=v; f:=0;
c:=ic; w:=iw;
next:=g[u];
end;
g[u]:=size;
inc(size);
with mem[size] do begin
n:=u; f:=0;
c:=0; w:=-iw;
next:=g[v];
end;
g[v]:=size;
end;
procedure init;
var i,j,k,u,v,c,w,code:longint;
begin
readln(row,col);
for i:=1 to row do
for j:=1 to col do
read(hori[i,j]);
for i:=1 to row do
for j:=1 to col do
read(vert[i,j]);
st:=(row*col+1); trm:=(row*col+2); n:=(row*col+2);
code:=0; size:=1;
for i:=1 to row do
for j:=1 to col do begin
inc(code);
if hori[i,j]=0 then continue;
inc(tot);
if (i xor j) and 1 = 1 then begin
insnbs(st,code,1,0);
if i>1 then insnbs(code,code-col,1,vert[i,j]+vert[i-1,j]);
if i<row then insnbs(code,code+col,1,vert[i,j]+vert[i+1,j]);
if j>1 then insnbs(code,code-1,1,hori[i,j]+hori[i,j-1]);
if j<col then insnbs(code,code+1,1,hori[i,j]+hori[i,j+1]);
end else insnbs(code,trm,1,0);
end;
end;
function augment(u,f:longint):longint;
var j,k:longint;
t1:pnode;
begin
if u=trm then begin
inc(flow,f);
inc(cost,f*dist);
exit(f);
end;
v[u]:=true; j:=f;
t1:=g[u];
while t1<>0 do begin
if (mem[t1].c>0)and(not v[mem[t1].n])and(mem[t1].w=0) then begin
k:=augment(mem[t1].n,min(j,mem[t1].c));
dec(j,k);
dec(mem[t1].c,k); inc(mem[t1 xor 1].c,k);
inc(mem[t1].f,k); dec(mem[t1 xor 1].f,k);
if j=0 then break;
end;
t1:=mem[t1].next;
end;
exit(f-j);
end;
function relabel:boolean;
var i,j,k,d:longint;
t1:pnode;
begin
d:=maxint;
for i:=1 to n do if v[i] then begin
t1:=g[i];
while t1<>0 do begin
if (mem[t1].c>0)and(not v[mem[t1].n])and(mem[t1].w<d) then
d:=mem[t1].w;
t1:=mem[t1].next;
end;
end;
if d=maxint then exit(false);
for i:=1 to n do if v[i] then begin
t1:=g[i];
while t1<>0 do begin
dec(mem[t1].w,d);
inc(mem[t1 xor 1].w,d);
t1:=mem[t1].next;
end;
end;
inc(dist,d);
exit(true);
end;
procedure zkw;
begin
dist:=0;
repeat
repeat
fillchar(v,sizeof(v),0);
until augment(st,maxint)=0;
until not relabel;
end;
procedure answer;
var i,j,k,x,y,x1,y1:longint;
t1:pnode;
begin
fillchar(ans,sizeof(ans),0);
if flow<<1=tot then
writeln(cost)
else writeln(flow);
x:=1; y:=1;
for x:=1 to row do
for y:=1 to col do if (hori[x,y]<>0)and((x xor y) and 1 = 1) then begin
t1:=g[(x-1)*col+y];
while t1<>0 do begin
if (mem[t1].n<st)and(mem[t1].f>0) then begin
if mem[t1].n mod col = 0 then begin
x1:=mem[t1].n div col;
y1:=col;
end else begin
x1:=mem[t1].n div col +1;
y1:=mem[t1].n mod col;
end;
if (x=x1) then begin
ans[x,y]:=1;
ans[x1,y1]:=1;
end else begin
ans[x,y]:=2;
ans[x1,y1]:=2;
end;
break;
end;
t1:=mem[t1].next;
end;
end;
for x:=1 to row do begin
for y:=1 to col-1 do
write(ans[x,y],' ');
writeln(ans[x,col]);
end;
end;
begin
init;
zkw;
answer;
end.