Блог пользователя rmn

Задача "Длинный путь в графе" (ОНЗИ)
Автор rmn, 10 лет назад, По-русски

Условие задачи

В оригинальном условии задачи ограничение на количество вершин N ≤ 10.
В разборе к этой задаче есть упражнение: решить задачу для N ≤ 50 c помощью динамического программирования.

Подскажите, пожалуйста, как решить задачу при N ≤ 50.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

Не знаю насчёт ДП, но возведением матрицы в степень, кажется, её можно решить.

Случай, когда C <= кратчайшего пути между v1 и v2 — тривиальный, также как и случай, когда пути нет вообще. Пусть C > кратчайшего пути. Возведем матрицу в степень C и посмотрим на (i, j) элемент. Если там не ноль, то путь длины C есть, и ответ "Yes 0". Если там ноль, то есть путь длины C+1 (можно дойти до конечной вершины и дальше крутиться вокруг неё) и ответ "No 1".

UPD Я затупил, последнее верно только для неориентированного графа. С ориентированным вроде можно проверить 50 соседних степеней матрицы влево и 50 вправо :)

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    Действительно, я как-то сразу не додумался что ответ, если он существует, будет лежать либо недалеко от C, либо в каких-то маленьких степенях матрицы ( ≤ 50).

    Спасибо!

    → Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Не знаю насчёт ДП, но возведением матрицы в степень, кажется, её можно решить.

    Если уж придраться к терминологии, то возведение матрицы в степень — способ ускорения подсчета частного случая ДП.

    → Ответить