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

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

Начал прорешивать прошлые IOI, и столкнулся с проблемой, а именно с задачей Dreaming с первого тура IOI 2013, вроде как понятно жадное решение с радиусом деревьев, однако неуклонно получаю WA. Радиус нахожу так : беру любую вершину дерева (А), нахожу от нее самую дальнюю (B), и от B тоже дальнюю (С). Как диаметр беру путь B -> C, и восстанавливаю его. Если путь нечетной длины, то центр дерева это вершина посередине пути, иначе выбираю из двух кандидатов (тоже в середине) ту вершину, максимальное расстояние от которой до какой — то другой вершины минимально. И уже радиус дерева беру как макс. расстояние от центра до какой — то вершины. Правильно ли это?

Вот, собственно, код. ЧЯДНТ?

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

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

если дерево у вас взвешенное, то вот это "Если путь нечетной длины, то центр дерева это вершина посередине пути" кажется сомнительным. по крайней мере, если под центром дерева вы подразумеваете то же, что и теория графов.

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

    Разве веса меняют тот факт, что центр дерева лежит на самом длинном пути?

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

      Сомнительно то, что если вы считаете расстояния между вершинами не реберно, а с весами, то центром у вас будет вершина именно на середине пути.

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

        Все, понял свой косяк, исправил — 100. Спасибо за помощь :)