ASSIGN1 - Phân công hoàn thành sớm nhất
Tác giả: ll931110
Ngôn ngữ: Pascal
program ASSIGN1;
const
input = '';
output = '';
maxn = 200;
maxv = high(longint);
var
a: array[1..maxn,1..maxn] of longint;
n,res: longint;
q,trace,matchx,matchy: array[1..maxn] of longint;
procedure init;
var
fi: text;
i,j: longint;
begin
assign(fi, input);
reset(fi);
readln(fi, n);
for i := 1 to n do
for j := 1 to n do read(fi, a[i,j]);
close(fi);
end;
function FindPath(x: longint): longint;
var
front,rear: longint;
i,j: longint;
begin
front := 1; rear := 0;
fillchar(trace, sizeof(trace), 0);
for i := 1 to n do if matchx[i] = 0 then
begin
inc(rear); q[rear] := i;
end;
while front <= rear do
begin
i := q[front];
inc(front);
for j := 1 to n do
if (trace[j] = 0) and (a[i,j] <= x) and (matchy[j] <> i) then
begin
trace[j] := i;
if matchy[j] = 0 then exit(j);
inc(rear); q[rear] := matchy[j];
end;
end;
exit(0);
end;
procedure Enlarge(f: longint);
var
x,next: longint;
begin
repeat
x := trace[f];
next := matchx[x];
matchx[x] := f;
matchy[f] := x;
f := next;
until f = 0;
end;
function ok(x: longint): boolean;
var
nm,fin: longint;
begin
nm := 0;
fillchar(matchx, sizeof(matchx), 0);
fillchar(matchy, sizeof(matchy), 0);
repeat
fin := FindPath(x);
if fin = 0 then break;
inc(nm);
Enlarge(fin);
until false;
ok := nm = n;
end;
procedure solve;
var
inf,sup,med: longint;
begin
inf := 0;
sup := maxv;
repeat
med := (inf + sup) div 2;
if ok(med) then
begin
res := med;
sup := med - 1;
end
else inf := med + 1;
until inf > sup;
end;
procedure printresult;
var
fo: text;
begin
assign(fo, output);
rewrite(fo);
writeln(fo, res);
close(fo);
end;
begin
init;
solve;
printresult;
end.