|
x, y : array [1..maxn] of boolean;
lx, ly : array [1..maxn] of longint;
map : array [1..maxn,1..maxn] of longint;
procedure prepare;
var i, j : longint;
begin
for i:=1 to n do
for j:=1 to n do
if map[i,j]>lx[i] then lx[i]:=map[i,j];
end;
function search(k : longint) : boolean;
var i : longint;
begin
search:=true; x[k]:=true;
for i:=1 to n do
if not y[i] and (lx[k]+ly[i]=map[k,i]) then begin
y[i]:=true; tmp:=match[i]; match[i]:=k;
if (tmp=0) or search(tmp) then exit;
match[i]:=tmp;
end;
search:=false;
end;
procedure km;
var i, j, k : longint;
begin
for k:=1 to n do
repeat
fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
if search(k) then break;
d:=maxlongint;
for i:=1 to n do
if x[i] then
for j:=1 to n do
if not y[j] then
if lx[i]+ly[j]-map[i,j]<d then d:=lx[i]+ly[j]-map[i,j];
for i:=1 to n do begin
if x[i] then dec(lx[i],d);
if y[i] then inc(ly[i],d);
end;
until false;
end;
procedure getans;
var ans, i : longint;
begin
ans:=0;
for i:=1 to n do
inc(ans,map[match[i],i]);
end;
|
