Задание 2. Решение задачи «Вершинное покрытие» методом перебора сочетаний

Уточнение: в алгоритме перебора сочетаний отразить оптимизацию перебора для k>n/2, как было обсуждено на лекции.


Тестовый файл: VC1.txt

Формат файла:

1-я строка:

     n m

где n - количество вершин, m - количество дуг

Потом - m строк, в каждой строке номера вершин-концов ребра, через пробел.

Вершины нумеруются от 1 до n.

 

Программа получает на вход 4 параметра – пути к текстовым файлам:

1.[Вход] Файл входными данными, описанного выше формата.

2.[Выход] Файл с результатом – оптимальным покрытием. Содержит одну строку, в которой через пробел указаны номера вершин, входящих в покрытие. Нумерация – от 1.

3.[Выход] Файл с результатом – стоимостью оптимального решения (мощность минимального покрытия). Содержит 1 строку с натуральным числом.

4.[Выход] Файл с замером временной сложности. Файл с двумя строками. В первой строке – время расчёта в секундах (с точностью до 3 знаков после запятой, т.е. до миллисекунд). Во второй строке – количество операций. Операциями считаем операции присваивания и сравнения элементов массивов (массива A и вспомогательных массивов/других структур).