Лабораторные. Дерендеева
1 работа
Построить минимальное связывающее дерево заданного множества точек на плоскости в прямоугольной метрике (d(M,N)=|XM-XN|+|YM-YN|)
Метод решения
Алгоритм Борувки-Краскла.
Пример
5
1 2
3 6
-1 -2
4 4
3 10
Файл входных данных
Множество точек на плоскости, заданное парами координат (x,y).
N - количество точек. Далее построчно координаты точек.
Файл выходных данных
Минимальное связывающее дерево, заданное в виде списков смежностей.
Для каждой точки исходного множества указать порядковые номера точек, смежных с ней. Список начинать с новой строки, точки внутри списка упорядочить по возрастанию номеров. Каждый список заканчивается 0. В последней строке файла записать вес.
2 работа
Пусть {A1,…,An} - пpоизвольная последовательность множеств (необязательно непеpесекающихся).
Системой pазличных пpедставителей для {A1,…,An} называется последовательность попаpно pазличных элементов {a1,…,an} такая, что ai пpинадлежит Ai.
Найти систему pазличных пpедставителей для заданной последовательности множеств, если она существует.
Файл входных данных
Множества Ai являются наборами натуральных чисел.
Последовательность {A1,…,An} задана числом n - количество множеств, далее в каждой строке перечислены элементы очередного множества, множества заканчиваются нулем.
Файл выходных данных
Y и во второй строке система представителей a1 … an (натуральные числа разделенные пробелами) или N.