Лабораторные. Нестерова

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 работа

Построить максимальный поток f в заданной сети.

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

алгоpитм Фоpда-Фалкеpсона.

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

Сеть, заданная матрицей пропускных способностей.

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

Далее построчно расположена матрица пропускных способностей размерности NxN.

В предпоследней и последней строках файла записаны источник s и сток t.

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

Матрица f, расположенная построчно.

В последней строке файла записать величину потока |f|.