Нахождение максимальных паросочетаний

Рассмотрим неориентированный двудольный граф G из N вершин. Паросочетанием в нем называется некоторый набор ребер этого графа, в котором никакие два ребра не имеют общей вершины. Размер паросочетания - количество в нем ребер. Данный алгоритм находит максимальное паросочетание в графе.

Занумеруем отдельно вершины левой и правой долей графа (доли A и B соответственно). Пусть M и N - размеры долей A и B соответственно. Пусть также G[i,j]=true в том случае, если есть ребро из вершины i доли A в вершину j доли B. Будем записывать решение в массивы ASol и BSol размеров M и N соответственно, где ASol[i]=0, если вершина i доли A не входит в паросочетание; иначе ASol[i] - номер вершины из доли B, с которой соединена i-я вершина в доле A. Аналогично определяется BSol[i].

Будем делить все ребра на две группы: входящие в текущее паросочетание (обратные) и не входящие в него (прямые). Вначале все ребра прямые. Легко проверить, является ли ребро, соединяющее i-ю вершину доли A с j-й вершиной доли B, обратным: это верно в том случае, когда ASol[i]=j (или BSol[j]=i). Назовем чередующимся путем такой путь в графе из некоторой вершины доли A в некоторую вершину доли B, oчто для любых двух последовательных вершин C и D из этого пути верно следующее: если С лежит в доле A, а D - в доле B, то ребро (C,D) прямое; иначе оно обратное. (В силу двудольности графа вершины C и D не могут лежать в одной доле.)

Идея алгоритма следующая: находим в графе чередующиеся пути и разворачиваем их, пока не сможем найти очередной чередующийся путь; в этом случае работа алгоритма завершается и построенное паросочетание (записанное в ASol и BSol) будет максимальным. Разворот пути заключается в следующем: мы меняем статус каждого из его ребер на противоположный, т. е. прямое ребро становится обратным, а обратное - прямым. Заметим, что при этом размер нашего паросочетания увеличивается на единицу. Мы будем перебирать чередующиеся пути, по одному для каждой начальной вершины.

Реализация алгоритма:

const
  MaxN = 100;
  MaxM = MaxN;

var
  M,N : Integer;
  G : array [1 .. MaxN,1 .. MaxN] of Boolean;
  Cur,ACur : Integer;
  ASol,BSol,Prev : array [1 .. MaxN] of Integer;
  Ql,Qr : Integer;
  Q : array [1 .. MaxN*2+1] of Integer;

function PBFS(A : Integer) : Boolean;
var
  B : integer;
  Found : Boolean;
begin
  fillchar(Prev,sizeof(Prev),0);
  Ql := 1;
  Qr := 1;
  Q[1] := A;
  Found := false;
  while (Qr>=Ql) and not Found do
  begin
    Cur := Q[Ql];
    Inc(Ql);
    for B:=1 to N do
      if G[Cur,B] then
      begin
        ACur := B;
        if BSol[ACur]=0 then
        begin
          Found := true;
          break;
        end
        else if Prev[Bsol[ACur]]=0 then
        begin
          Prev[BSol[ACur]]:=Cur;
          inc(Qr);
          Q[Qr]:=BSol[ACur];
        end;
      end;
     end;
     PBFS:=Found;
end;

procedure PMax;
var
  A,B : Integer;
  Tmp : Integer;
begin
  fillchar(ASol,sizeof(ASol),0);
  fillchar(BSol,sizeof(BSol),0);
  for A:=1 to M do
    if PBFS(A) then
      while Cur<>0 do
      begin
        Tmp:=ASol[Cur];
        BSol[ACur]:=Cur;
        ASol[Cur]:=ACur;
        Cur:=Prev[Cur];
        ACur:=Tmp;
      end;
end;

Процедура PBFS делает O(N^2) действий, и ее вызывают N раз; значит, время работы алгоритма - O(N^3). Требуется O(N) дополнительной памяти.