Страница: 1 [Всего задач: 3]      

Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин.

Входные данные
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.

Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.

Пример входного файла
4
1 2
1 3
2 3
2 4

Пример выходного файла
2
1 2 4
3

Прислать комментарий

Решение

Жюри решило поздравить авторов метода Форда-Фалкерсона, алгоритмов Флойда-Беллмана, Кнута-Морриса-Пратта, формы Бэкуса-Науэра, схемы Ривеста-Шамира-Адлемана и других классиков Computer Science с наступающим 4 июля (Днем независимости). Для этого было куплено N открыток и M конвертов. К сожалению, конверты и открытки оказались разных размеров, и некоторые открытки помещаются не во все конверты. Напишите программу, находящую такое распределение открыток по конвертам, при котором поздравления получат наибольшее число классиков Computer Science. В один конверт разрешается вкладывать не более одной открытки. 

Входные данные
В первой строке входного файла записаны числа M и N (0 ≤ M, N ≤ 100). Далее записаны высота и ширина каждого из M конвертов, затем – высота и ширина каждой из N открыток. Размеры конвертов и открыток являются натуральными числами, не превосходящими 32767, и разделяются пробелами и/или символами перевода строки.

Выходные данные
Выведите в выходной файл целое число K – максимальное количество открыток, которые можно разложить по конвертам. Далее выведите K пар целых чисел, означающих номер открытки и номер конверта, в который ее необходимо положить.

Пример входного файла
4 4
3 3 141 282 282 141 200 100
3 1 140 280 141 282 201 1

Пример выходного файла
4
1 1 2 3 3 2 4 4

Прислать комментарий

Решение

В деревне живут N девушек и столько же юношей. Каждый юноша оценивает всех девушек числами от 1 до N (разных девушек – разными числами), а каждая из девушек аналогичным образом оценивает юношей. Устойчивым паросочетанием называется такое взаимно-однозначное соответствие между юношами и девушками, что для любых двух юношей Ю₁ и Ю₂ и соответствующих им девушек Д₁ и Д₂ выполняются следующие два условия: 
    1) либо Ю₁ оценивает Д₁ выше, чем Д₂ , либо Д₂ оценивает Ю₂ выше, чем Ю₁ ; 
    2) либо Ю₂ оценивает Д₂ выше, чем Д₁ , либо Д₁ оценивает Ю₁ выше, чем Ю₂.
Напишите программу, которая по заданным оценкам находит некоторое устойчивое паросочетание.

Входные данные
Первая строка входного файла содержит целое число N (1 ≤ N ≤ 200). В строках с номерами от 2 до N+1 находятся наборы из N чисел, которыми юноши с номерами от 1 до N оценивают девушек. В строках с номерами от N+2 до 2N+1 находятся наборы из N чисел, которыми девушки оценивают юношей. Числа в наборах разделяются пробелами.

Выходные данные
В выходной файл выведите номера девушек, соответствующих юношам с номерами от 1 до N по порядку. Числа должны быть разделены пробелами и/или символами перевода строки.

Пример входного файла
3
1 2 3
2 3 1
1 2 3
1 2 3
2 3 1
3 1 2

Пример выходного файла
3 2 1

Прислать комментарий

Решение

Страница: 1 [Всего задач: 3]