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

Автор KimJennie, история, 2 года назад, По-русски

Решал Ашку с тренировки СПбГУ (здесь) и у меня постоянно МЛЕ на 9-тесте. Подумал, что это из-за интов и заменил на шортЫ, теперь из интов только длины ребер. Но теперь у меня ТЛЕ. Прошу помочь решить эту задачу

Вот мой код с МЛЕ: https://pastebin.com/u8CkbhrE

Вот с ТЛЕ: https://pastebin.com/V8txT7KM

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

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

Алгоритм Краскала работает за $$$O(E\log{V})$$$. Алгоритм Прима (как и алгоритм Дейкстры) в варианте для плотных графов (без set или priority_queue) работает за $$$O(V^2)$$$.

В этой задаче $$$E \sim V^2$$$. Используя алгоритм Краскала, вы добавляете лишний логарифм. При $$$V = 5000$$$ решение со сложностью $$$V^2$$$ уложится в TL, со сложностью $$$V^2\log{V}$$$ — уже нет.

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

https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree

А еще можно написать триангуляцию, написать O(NlogN) и вообще не смотреть на TL