Где применяется
1. Задача
Ты соединяешь сетью несколько точек: офисы, электростанции, водонапорные баки. Есть список возможных связей, у каждой своя цена. Нужно соединить все точки так, чтобы из любой можно было добраться до любой другой, и заплатить в сумме как можно меньше. Связь, которая замыкает петлю, всегда лишняя: её концы и так достижимы друг из друга, и деньги на неё потрачены зря.
Такой набор связей (все узлы соединены, петель нет, суммарный вес наименьший) называют минимальным остовным деревом.
В прошлом уроке ты построил union-find (DSU): он объединяет две группы и отвечает на вопрос «это одна группа?» почти за постоянное время. Алгоритм Краскала опирается ровно на эти две операции.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где нужен самый дешёвый способ соединить всё или нужно знать, какие связи обязательны в самой дешёвой сети. Отсортируй рёбра по весу и добавляй каждое, чьи концы ещё не соединены, а это проверяет union-find.
Каждая пара точек это ребро с весом в манхэттенское расстояние, около 5 на 10^5 рёбер для 1000 точек, и Краскал их соединяет.
Отсортируй по лимиту и запросы, добавляй каждое ребро меньше текущего лимита и отвечай на каждый запрос одним find.
- 1489.Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (откроется в новой вкладке)Сложная
Запусти Краскала один раз без каждого ребра и один раз с этим ребром заранее, и сравни каждую сумму с настоящим минимумом.