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

Автор beched, 10 лет назад, По-русски

Привет!

Не получается придумать оптимальное решение для следующей задачи: дан ориентированный граф (городов), вершины пронумерованы по DFS (pre-order).

Говорим, что город w снабжает город v, если все пути из корня (вершины 1) в v проходят через w.

Для каждого города нужно посчитать количество городов, которые он снабжает. Всего городов 1000, дорог (однонаправленных рёбер) 2000. Решить можно в лоб, перечисляя все пути через BFS или DFS, но это экспонента, не годится.

Думал о всяких рекурсивных методах, имея в виду такое наблюдение: если город w не снабжает город v, то он не снабжает и всех потомков v.

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

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А нельзя по очереди удалять вершины и говорить что w снабжает v если до удаления v было достижимо, а после удаления перестало? Это должно за квадрат работать.

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

    Хм, ну, не за квадрат, потому что матрицу достижимости ещё надо за куб построить (алгоритм Флойда-Уоршелла), но надо попробовать...

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

      Ну тогда уж V Дейкстр с кучей за VElogE

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

        Стоп а зачем?

        Запустим dfs(1) и запомним все посещенные вершины. После удаления еще раз запустим dfs(1) и сравним

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

          О, а это ведь очевидная мысль... Сейчас попробую.

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

      А ещё надо ведь перестраивать матрицу достижимости для графа с удалённой вершиной каждый (квадрат) раз...

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Можно попробовать посчитать ДП, сколько способов добраться от вершины i до j. Тогда город w будет снабжать город v, если dp1v = dp1w·dpwv

»
10 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

В общем, задача была решена последовательным запуском dfs с пропуском каждой из вершин. Выходит, за квадрат о_О

При этом, как оказалось, я не до конца понял условие, и там ещё важно, что если несколько городов удовлетворяют условию снабжения, то выбирается один с наибольшим номером, поэтому идти надо от последнего к первому, запоминая города, которые кем-то уже снабжены.

Спасибо grikukan! =)

»
10 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

Линейным алгоритмом находишь все точки сочленения. А дальше все понятно. http://e-maxx.ru/algo/cutpoints