Длинный путь в графе
Заданы N-вершинный ориентированный граф с двумя выделенными вершинами
v1
и v2
и целое число C. Требуется:
1) определить, существует ли в заданном графе путь из вершины v1
в вершину v2, состоящий из C ребер (путь может иметь самопересечения как по
вершинам, так и по ребрам);
2) найти минимум функции |
X
-
C
|, где X – количество ребер в некотором пути из v1
в v2
.
Входные данные
Первая строка входного файла содержит целое число N – количество вершин в
графе (1 ≤ N ≤ 10). В следующих N строках расположена матрица
N × N из нулей и единиц, элемент (i, j) которой равен единице, если в графе есть ребро из
вершины i в вершину j, и нулю, если такого ребра нет. (Граф может содержать
петли, т.е. ребра, идущие из вершины в саму себя). Элементы матрицы во
входном файле записаны без разделительных пробелов.
Наконец, строка N+2 содержит номера вершин v1
и v2
, а строка N+3 – десятичную запись числа C (1 ≤ C <
1050).
Выходные данные
В первую строку выходного файла выведите ответ на первый пункт задачи:
«Yes», если путь длины C существует, и «No», если нет. Во вторую строку
запишите ответ на второй пункт задачи. Если ни одного пути из v1
в v2
не существует, ваша программа должна вывести -1.
Пример входного файла
3
010
001
100
1 1
555555555555555555555555555555555
Пример выходного файла
Yes
0
Решение
Достаточно решить второй пункт задачи. Пусть Ai
– множество вершин, в которые мы можем попасть из вершины v1
, пройдясь по k ребрам. Будем последовательно вычислять множества A0
, A1
, A2
и т. д. Когда какое-то из этих множеств повторится, это означает, что рассматриваемая последовательность
вошла в цикл (а это произойдет не позднее, чем через 2N ≤ 210
= 1024 шагов). Если число C достаточно большое, то с помощью деления определяем позицию
цикла, которой оно соответствует. Далее находим ближайшее к этой позиции
множество, содержащее v2
. Здесь нужно внимательно разобрать возможные
случаи, не забывая про существование предпериода.
Упражнение
Решите ту же самую задачу методом динамического программирования при
ограничении N ≤ 50.