Теоретический материал

Программа решения за N^3

begin {Main}

  fillchar(res,sizeof(res),0);

  fillchar(u,sizeof(v),0);

  fillchar(v,sizeof(v),0);

  …{задание исходных данных}

  for i:= 1 to n do

  {каждой вершине одного из множеств находим назначение}

    begin

      for j:=1 to n do min[j]:=maxint;{минимальные значения столбцов}

      fillchar(new,sizeof(new),false);

      j0 := 0;

      res[0] := i;

      repeat

       del:=maxint;

       new[j0] := true;{в данной версии мы метим столбцы!!!}

       i0 := res[j0];

       for j := 1 to n do

         if not new[j] then begin

           if a(i0,j)-u[i0]-v[j] < min[j] then begin

            min[j] := a(i0,j)-u[i0]-v[j];

            way[j] := j0

           end;

           if min[j] < del then begin

            del := min[j];

            j1 := j

           end

         end;{нашли новое значение del}

       for j := 0 to n do

         if new[j] then begin

           u[res[j]] := u[res[j]] + del;

           v[j]:=v[j]-del;

         end

         else min[j] := min[j] - del;{пересчитываем минимумы}

         j0 := j1; {}

       until res[j0]=0; {свободный ноль позволит увеличить паросочетание}

    repeat {перестраиваем цепочку с учетом выбранного нуля}

      j1 := way[j0];

      res[j0] := res[j1];

      j0 := j1

    until j0 = 0;

  end;

  writeln(-v[0]); {здесь мы получили сумму всех назначений}

  for j:= 1 to n do

    writeln(a(res[j],j));

end.