Контрольная работа: Алгоритмы на графах. Независимые и доминирующие множества

0 … 0

В нашей задаче определены стоимости вершин графа или стоимости столбцов матрицы А*, и необходимо найти разбиение наименьшей стоимости. Пусть стоимости описываются в массиве Price (Price:array [1..MaxN] of integer ) и для примера на рисунке имеют значения [15 13 4 3 8 9 10]. Осталась чисто техническая деталь – отсортировать элементы каждой строки матрицы Bl по возрастанию стоимости соответствующих столбцов матрицы А. Логика формирования приведена ниже по тексту (Blocs).

procedure Blocs; {выделения блоков}

{Bl – глобальная переменная}

procedure Sort;

{Price и Bl – глобальные переменные}

begin

…

end;

procedure Press (i, j:integer); {Сдвигаем элементы строки с номером i, начиная с позиции (столбца) j, на одну позицию вправо}

{Bl – глобальная переменная}

var k:integer;

begin

k:=j;

while Bl [i, k]<>0 do begin {Поэтому размерность матрицы с плюс единицей. В последнем столбце строки всегда записан 0.}

Bl [i, k]:=Bl [i, k+1];

Inc(k);

end; {while}

end; {Press}

var i, j, cnt:integer;

begin

FillChar (Bl, SizeOf(Bl), 0);

for i:=1 to N do Bl [1, i]:=i; {предполагается, что в первом блоке все столбцы}

for i:=1 to N-1 do begin

j:=1; cnt:=0;

while Bl [i, j]<>0 do begin

if A*[i, Bl [i, j]]=0 then begin {столбецневэтомблоке}

Inc(cnt);

Bl [i+1, cnt]:=Bl [i, j]; {переписать в следующую строку}