Лабораторные. Рылов

1 работа

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

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

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

Пример

  (25)
1------2
|      |(0)
+------3--------4
  (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 работа

Пусть {A1,…,An} - пpоизвольная последовательность множеств (необязательно непеpесекающихся). Системой pазличных пpедставителей для {A1,…,An} называется последовательность попаpно pазличных элементов {a1,…,an} такая, что ai пpинадлежит Ai.

Найти систему pазличных пpедставителей для заданной последовательности множеств, если она существует.

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

Множества Ai являются наборами букв латинского алфавита.

Последовательность {A1,…,An} задана числом n - количество множеств, далее в каждой строке перечислены элементы очередного множества - маленькие латинские буквы, множества заканчиваются символом 0 (нуль).

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

Y и во второй строке система представителей a1 … an (маленькие латинские буквы разделенные пробелами) или N.