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.

Download