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

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

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

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

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

Вот

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

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

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

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

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