ASSIGN1 - Phân công hoàn thành sớm nhất
Tác giả: RR
Ngôn ngữ: Pascal
var
l,r,res,mid,i,j,n:longint;
a,c:array[1..222,1..222] of longint;
trace,matchX,matchY,queue:array[1..222] of longint;
function findPath(x:longint):longint;
var
u,v,first,last:longint;
begin
fillchar(trace,sizeof(trace),0);
first:=1; last:=1; queue[1]:=x;
while first<=last do
begin
u:=queue[first]; inc(first);
for v:=1 to n do
if (trace[v]=0) and (matchY[v]<>u) and (c[u,v]=1) then
begin
trace[v]:=u;
if matchY[v]=0 then exit(v);
inc(last); queue[last]:=matchY[v];
end;
end;
exit(0);
end;
procedure enlarge(y:longint);
var
x,next:longint;
begin
while y<>0 do
begin
x:=trace[y];
next:=matchX[x];
matchX[x]:=y;
matchY[y]:=x;
y:=next;
end;
end;
function check(val:longint):boolean;
var
x,y:longint;
begin
fillchar(matchX,sizeof(matchX),0);
fillchar(matchY,sizeof(matchY),0);
for x:=1 to n do
for y:=1 to n do
if a[x,y]<=val then c[x,y]:=1
else c[x,y]:=0;
for x:=1 to n do
begin
y:=findPath(x);
if y<>0 then enlarge(y);
end;
y:=0;
for x:=1 to n do
if matchX[x]<>0 then inc(y);
exit(y=n);
end;
begin
read(n);
for i:=1 to n do
for j:=1 to n do
read(a[i,j]);
l:=1; r:=1000111; res:=1000111;
while l<=r do
begin
mid:=(l+r) shr 1;
if check(mid) then
begin
r:=mid-1;
res:=mid;
end
else l:=mid+1;
end;
writeln(res);
end.