Лабораторные. Петрова

1 работа

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

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

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

Пример

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

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

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

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

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

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

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

2 работа

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

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

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

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

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

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

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

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

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

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

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