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

Не могу решить задачу на нахождение минимального остовного дерева.
Автор Kig1337, 11 лет назад, По-русски

http://mirror.codeforces.com/gym/100088/attachments задача А. Помогите пожалуйста, желательно реализация без контейнеров, на обычных массивах.

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

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

Вот

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

    можете пояснить код?

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

      Алгоритм Прима, работающий за O(n2 + m). Суть:

      • добавляем по одной вершинке в mst;
      • для каждой вершинки храним минимальное расстояние до mst;
      • при добавлении выбираем вершинку, которая ближе всех к mst;
      • после добавления вершинки обновляем массив минимальных расстояний от mst до каждой вершинки.
      → Ответить