NKBM - Cặp ghép cực đại trên đồ thị hai phía

Tác giả: RR

Ngôn ngữ: Pascal

const
  MAXN=1011;
type
  list=^node;
  node=record
        u:longint;
        next:list;
  end;

procedure add(u:longint; var a:list);
    var
      p:list;
    begin
      new(p); p^.u:=u;
      p^.next:=a; a:=p;
    end;

var
  n,m,k,u,v,x,y:longint;
  ke:array[1..MAXN] of list;
  matchX,matchY,trace,queue:array[1..MAXN] of longint;

function findPath(x:longint):longint;
    var
      u,v,first,last:longint;
      p:list;
    begin
      fillchar(trace,sizeof(trace),0);
      first:=1; last:=1; queue[1]:=x;
      while first<=last do
        begin
          u:=queue[first]; inc(first);
          p:=ke[u];
          while p<>nil do
            begin
              v:=p^.u; p:=p^.next;
              if (trace[v]=0) and (matchY[v]<>u) then
                begin
                  trace[v]:=u;
                  if matchY[v]=0 then exit(v);
                  inc(last); queue[last]:=matchY[v];
                end;
            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;

begin
  read(n,m,k);
  for k:=1 to k do
    begin
      read(u,v);
      add(v,ke[u]);
    end;

  for x:=1 to n do
    begin
      y:=findPath(x);
      enlarge(y);
    end;

  y:=0;
  for x:=1 to n do
    if matchX[x]<>0 then inc(y);
  writeln(y);
end.

Download