Why I get wrong?
Posted by
dejiyu 2 Apr 2008 19:34
program djy;
var
a:array[1..150,1..150] of integer;
lx,ly,link:array[1..150] of integer;
flagx,flagy:array[1..150] of boolean;
n:longint;
procedure init;
var
i,j:longint;
begin
readln(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
end;
procedure prepare;
var
i,j,s:longint;
begin
{for i:=1 to n do
begin
s:=0;
for j:=1 to n do
s:=s+a[j,i];
for j:=1 to n do
a[j,i]:=a[j,i]-s;
end;}
fillchar(lx,sizeof(lx),0);
fillchar(ly,sizeof(ly),0);
for i:=1 to n do
for j:=1 to n do
if a[i,j]>lx[i] then lx[i]:=a[i,j];
end;
function find(i:longint):boolean;
var
j:longint;
begin
flagx[i]:=true;
for j:=1 to n do
if (lx[i]+ly[j]=a[i,j]) and (flagy[j]=false) then
begin
flagy[j]:=true;
if (link[j]=0) or (find(link[j])=true) then
begin
link[j]:=i;
find:=true;
exit;
end;
end;
find:=false;
end;
procedure main;
var
i,j,k,d:longint;
begin
fillchar(link,sizeof(link),0);
for k:=1 to n do
repeat
fillchar(flagx,sizeof(flagx),false);
fillchar(flagy,sizeof(flagy),false);
if find(k)=true then break;
d:=maxint;
for i:=1 to n do
for j:=1 to n do
if (flagx[i]=true) and (flagy[j]=false) and (lx[i]+ly[j]-a[i,j]<d) then d:=lx[i]+ly[j]-a[i,j];
for i:=1 to n do
if flagx[i]=true then lx[i]:=lx[i]-d;
for i:=1 to n do
if flagy[j]=true then ly[j]:=ly[j]+d;
until false;
end;
procedure print;
var
i,j,s:longint;
begin
s:=0;
for i:=1 to n do
for j:=1 to n do
s:=s+a[i,j];
for i:=1 to n do
s:=s-a[link[i],i];
writeln(s);
end;
begin
init;
prepare;
main;
print;
end.