Лабораторные. Юхатский

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афе

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

Метод решения: сведение к задаче о максимальном потоке и использование поиска в глубину для поиска f-дополняющих цепей (М-чеpедующихся).

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

Двудольный гpаф G=(X,Y,E), k=|X|, l=|Y|, заданный Х-списками смежностей.

X-списки смежностей: k штук списков смежностей по одному для каждой вершины x из X.

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

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

Y и во второй строке полное паросочетание, представленное массивом XПАРА, или N и во второй строке вершина xi, из которой поиск не удачен.