Задача 102790

Темы:    [ Динамическое программирование (прочее) ] [ Длинная арифметика как инструмент ] [ Графы (прочее) ]

Сложность: 3+ Классы: Название задачи: Длинный путь в графе .

Условие

Заданы N-вершинный ориентированный граф с двумя выделенными вершинами v₁ и v₂ и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v₁ в вершину v₂, состоящий из C ребер (путь может иметь самопересечения как по вершинам, так и по ребрам);
2) найти минимум функции | X - C |, где X – количество ребер в некотором пути из v₁ в v₂ .

Входные данные
Первая строка входного файла содержит целое число N – количество вершин в графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во входном файле записаны без разделительных пробелов. 

Наконец, строка N+2 содержит номера вершин v₁ и v₂ , а строка N+3 – десятичную запись числа C (1 &le C < 10⁵⁰).

Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи: «Yes», если путь длины C существует, и «No», если нет. Во вторую строку запишите ответ на второй пункт задачи. Если ни одного пути из v₁ в v₂ не существует, ваша программа должна вывести -1.

Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555

Пример выходного файла
Yes
0

Решение

Скачать архив тестов и решений

Достаточно решить второй пункт задачи. Пусть A_i – множество вершин, в которые мы можем попасть из вершины v₁ , пройдясь по k ребрам. Будем последовательно вычислять множества A₀ , A₁ , A₂ и т. д. Когда какое-то из этих множеств повторится, это означает, что рассматриваемая последовательность вошла в цикл (а это произойдет не позднее, чем через 2^N ≤ 2¹⁰ = 1024 шагов). Если число C достаточно большое, то с помощью деления определяем позицию цикла, которой оно соответствует. Далее находим ближайшее к этой позиции множество, содержащее v₂ . Здесь нужно внимательно разобрать возможные случаи, не забывая про существование предпериода.

Упражнение
Решите ту же самую задачу методом динамического программирования при ограничении N ≤ 50.

Источники и прецеденты использования

книга
предмет	информатика
Автор	Беров В., Лапунов А., Матюхин В., Пономарев А.
Название	Особенности национальных задач по информатике
Издательство	Триада-С
Год издания	2000
глава
Номер	1
Название	Динамическое программирование
Задача
Номер	13