ACMP 592: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) (Новая страница: «== Ссылка на задачу == * [http://acmp.ru/?main=task&id_task=592 ACMP #592 — Небоскреб] == Похожие задачи == * Инт…») |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 8: | Строка 8: | ||
Присваиваем каждому отрезку уникальный id. Добавляем отрезки [0; 0] в каждом столбце, объединяем отрезки в соседних столбцах при помощи DSU. | Присваиваем каждому отрезку уникальный id. Добавляем отрезки [0; 0] в каждом столбце, объединяем отрезки в соседних столбцах при помощи DSU. | ||
Строим граф "кто на кого падает"; вес ребра (a-b) — минимальное расстояние от части a до части b. Количество ячеек, на которое упадёт каждая из частей, | Строим граф "кто на кого падает"; вес ребра (a-b) — минимальное расстояние от части a до части b. Количество ячеек, на которое упадёт каждая из частей, равно кратчайшему расстоянию от этой части до дна. Эти расстояния можно найти алгоритмом Дейкстры. | ||
[[Category: Сборник задач: ACMP]] | [[Category: Сборник задач: ACMP]] | ||
[[Category: Задачи: Система непересекающихся множеств]] | [[Category: Задачи: Система непересекающихся множеств]] | ||
[[Category: Задачи: Алгоритм Дейкстры]] | [[Category: Задачи: Алгоритм Дейкстры]] | ||
Текущая версия от 18:01, 6 января 2016
Ссылка на задачу
Похожие задачи
Комментарии
Присваиваем каждому отрезку уникальный id. Добавляем отрезки [0; 0] в каждом столбце, объединяем отрезки в соседних столбцах при помощи DSU.
Строим граф "кто на кого падает"; вес ребра (a-b) — минимальное расстояние от части a до части b. Количество ячеек, на которое упадёт каждая из частей, равно кратчайшему расстоянию от этой части до дна. Эти расстояния можно найти алгоритмом Дейкстры.