Лабораторные. Ромасс

1 работа

Построить минимальный остов связного неориентированного взвешенного графа.

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

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

Пример

      25
    1-----2
  4 |     |0
    +-----3-----4
             7

     4
     32767    25     4 32767
        25 32767     0 32767
         4     0 32767     7
     32767 32767     7 32767

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

Граф, заданный матрицей весов.

N - количество вершин.

Далее построчно расположена матрица весов размерности NxN. Число 32767 означает, что данное ребро отсутствует

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

Остов T, заданный списками смежностей (для каждой вершины указываются смежные с ней вершины, вершины отделяются друг от друга пробелами, в конце списков смежных вершин нули, каждый список с новой строки). Внутри каждого списка вершины упорядочить по возрастанию номеров. В последней строке файла записать вес (|T|).

2 работа

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

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

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

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

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

X-массив смежностей: также как и массив смежностей, только перечисляются смежные с вершинами x из X. Для изолиpованной веpшины индекс в массиве pавен 0.

В пеpвой стpоке файла числа k l. Во втоpой pазмеp массива. Далее pасположен массив смежности ( не более 10 чисел в одной стpоке).

Последний элемент массива pавен 32767.

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

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