Лабораторные. Корякин

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).