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

Автор Tekser15, история, 6 лет назад, По-русски

Всем здравствуйте, уже 2+ недели убил на задачу о кактусном графе, скрин условия -тут Сначала я пробовал делать через дейкстру для каждой вершины, поняв что веса по сути везде 1 решил сделать через бфс, однако и это решение требует хоть и меньше времени, однако также не проходит, прошу дать мне идею как решать, код думаю сам напишу, ибо идей уже не осталось по реализации этой задачи. Заранее всем спасибо.

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

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

up

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

Реально гроб). Есть идея о том, что можно аккуратно сжать все циклы и провести между ними ребра, так что это не ломало расстояния. И свести задачу к задаче на дереве + обработке отдельно циклов

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

    Может и можно, но вопрос как его разбить на такие ветки?

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

      Находишь цикли, теперь между пересекающими по одной вершине циклами ставишь ребро с весом 0, а если компоненты не пересекаются, а соединены ребром, то ставишь ребро с весом 1. И вроде на таком дереве уже все легко