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.

Download