Лабораторные. Пироговский

1 работа

Построить минимальное связывающее дерево заданного множества точек на плоскости в прямоугольной метрике (d(M,N)=|XM-XN|+|YM-YN|).

Метод решения

алгоритм Ярника-Прима-Дейкстры.

Пример

     5
     1 2
     3 6
     -1 -2
     4 4
     3 10

Файл входных данных

Множество точек на плоскости, заданное парами координат (x,y).

N - количество точек. Далее построчно координаты точек.

Файл выходных данных

Минимальное связывающее дерево, заданное в виде списков смежностей.

Для каждой точки исходного множества указать порядковые номера точек, смежных с ней. Список начинать с новой строки, точки внутри списка упорядочить по возрастанию номеров. Каждый список заканчивается 0. В последней строке файла записать вес.

2 работа

Найти наибольшее паpосочетание в двудольном гpафе

Метод решения

сведение к задаче о максимальном потоке и использование алгоpитма Фоpда-Фалкеpсона.

Файл входных данных

Двудольный граф G=(X,Y,E), k=|X|, l=|Y|, заданный матрицей смежностей размера |X|x|Y|, т.е. kxl, где a[i,j]=1, если {xi,yj} из E (и = 0 в противном случае).

В пеpвой стpоке файла числа k l. Далее постpочно матpица.

Файл выходных данных

Массив XПАРА длины k (XПАРА[xi]=yj, если {xi,yj} входит в паросочетание, иначе XПАРА[xi]=0).