| 1 Ладик Артём, 29 марта 2009 г. 12:34:46 | |
|
ладно, SOVA , уговорил.. нотвсе равно мне лично по как там они называются .. главное что я знаю как они работают и пишутся.... да и вообще если подумать.. то лучше использовать алгоритм Прима-Краскала...... наверно просто я его исп.. а там все намешано.. типа смесь самых лучших моментов из обоих алгоритмов)))
|
|
|
| 2 SOVA xxx, 29 марта 2009 г. 9:37:06 | |
что такое система непересекающихся множеств я знаю:)
я не знал что её можно назвать Dijoin-set))
To Ладик Артем: алгоритмы Прима и Краскала отличаются во многом:)
Прима мы постоянно строим дерево:
берем минимальное ребро добавляем в дерево
и потом еще n - 2 раза ищем минимальное ребро ИЗ ТЕХ ОДНА ВЕРШИНА КОТОРЫХ УЖЕ В ДЕРЕВЕ А ВТОРАЯ НЕТ
сложность O(N^2)
а алгоритм Краскала в конце получает дерево но чаще всего получает дерево из леса
первоначально каждая вершина в своей компоненте связности и потом отсортировав ребра по неубыванию весов
идем по всем ребрам и добавляем его если вершины которые соединяет ребро лежат в разных компонентах связности
сложность O(e log e) где e - количество ребер в графе я даже не уверен что на большом графе с множеством ребер одинакового веса алгоритм Прима и Краскала построят один и тот же остов
|
|
|
| 3 Соболев Евгений, 29 марта 2009 г. 1:54:46 | |
|
Например эту структуру данных нужно применять для решения задачи №78 с сайта e-olimp.com.ua, где ограничения на количество вершин до 125000 и ребер до 250000. И все это при TimeLimite в 0.3 сек...
|
|
|
| 4 Соболев Евгений, 29 марта 2009 г. 1:45:01 | |
|
Dijoin-Set - система непересекающихся множеств, поддерживает следующие операции: 1) создание нового множества; 2) объединение двух множеств; 3) нахождение множества к которому принадлежит заданный елемент. Пишется при помощи двух массивов, очень применима в алгоритме Крускала, почитать об этом можно на e-maxx.ru или в книге Кормена, Лейзерсона, Ривеста, Штайна "Алгоритмы. Построение и анализ"
|
|
|
| 5 Ладик Артём, 28 марта 2009 г. 23:21:31 | |
|
а по моему, SOVA, они одинаковы что прима что Краскала(Kruskal) ))))
|
|
|
| 6 SOVA xxx, 28 марта 2009 г. 22:35:41 | |
Нагин а что за Dijoin-Set на русский это как переводится или синонимы это названия?
а то я первый раз такую штуку слышу))
|
|
|
| 7 SOVA xxx, 28 марта 2009 г. 22:34:32 | |
за книжку пожалуста:)
кстати небольшая поправка - алгоритм каторый описывал Ладик Артем это алгоритм Краскала(Kruskal)
|
|
|
| 8 Нагин Сергей Юрьевич, 28 марта 2009 г. 15:30:25 | |
|
Dijoin-Set Рулет!!!!!!!
|
|
|
| 9 Карелин Виталий Александрович, 28 марта 2009 г. 13:57:01 | |
Ура! Сдал! И при n=8000, и здесь, на сайте, 'Города'.
Всем спасибо за участие,
SOVA xxx - отдельное спасибо за книжку)))
|
|
|
| 10 Григорьевых Данил Павлович, 28 марта 2009 г. 13:05:45 | |
|
Я решил "Города" ещё тогда, когда ничего кроме поиска в ширину не знал. Я просто запустил бинарный поиск по ответу (По времени прошло с лихвой, ибо сильной точности не требовалось).
|
|
|
| 11 Ладик Артём, 28 марта 2009 г. 12:37:52 | |
по поводу задачи "города"... советую просто изучить алгоритм прима... короче вот вкраце его суть
1) сортируем все ребра по неубыванию
2) перебираем все ребра от 1 до последнего
3) взяли iтое ребро
4) если 2 верщины этого ребра лежат в одной компоненте связности то это ребро пропускаем, а если в разных то добовляем его в дерево...
5) конец когда прошли все ребра
все ребра что мы добавляли и будут образовывать минимально остовное дерево
|
|
|
| 12 Карелин Виталий Александрович, 26 марта 2009 г. 22:21:22 | |
Кстати, спасибо за книжку - сейчас качаю.
И ты не мог бы посмотреть точно, как ты решил Города, пожалуйста))
|
|
|
| 13 Карелин Виталий Александрович, 26 марта 2009 г. 22:21:00 | |
Кстати, спасибо за книжку - сейчас качаю.
И ты не мог бы посмотреть точно, как ты решил Города, пожалуйста))
|
|
|
| 14 Карелин Виталий Александрович, 26 марта 2009 г. 22:18:38 | |
Неа, эта задача была на одном очном соревновании, текста в электронном виде нету ))
Основные моменты:
есть N точек, а вернее их координаты. Нужно найти минимальное L, такое,что если провести маршрут из любой точки в другую, то длина наибольшего сегмента не превысит L
2<=N<=8000 , 0<=Xi,Yi<=10000
Ограничение по времени 2 сек, память 16 Мб
Имхо, суть задачи полностью совпадает с 'Городами'
|
|
|
| 15 SOVA xxx, 26 марта 2009 г. 20:20:14 | |
http://proklondike.com/contentview.php?content=235
ссылка на очень классную книжку
там есть разбор Прима за квадрат и Краскала за e log e:)
и еще очень много полезных вещей
|
|
|
| 16 SOVA xxx, 26 марта 2009 г. 20:17:28 | |
кстати задача по-моему простая ведь вроде тот же радиус графа это и есть максимальная длина ребра
но еще смаря какой уровень задачи:) если нада выводить и сам граф то я думаю какой нить прим с использованием кучи или сортированных списков пойдет)если у них мощный сервак(как на тимусе) то 8000^2 просвистят тока так))
|
|
|
| 17 SOVA xxx, 26 марта 2009 г. 20:04:11 | |
наскока я помню города нада найти радиус графа и все! я не делал там примов и деревьев:)
а в этой задаче еще раз подумаю вроде в решение своем нашел косяк
слушай а эта задача в инете мб скинь ссылку там на месте почитаю условие и тесты:)
|
|
|
| 18 Карелин Виталий Александрович, 26 марта 2009 г. 18:55:56 | |
SOVA xxx:
Как ты хочешь ее решать? Можешь рассказать алгоритм, или выслать текст программы? Пожалуйста... Мне надо с ней разобраться...
|
|
|
| 19 Карелин Виталий Александрович, 26 марта 2009 г. 18:48:43 | |
|
По моему мнению,задача 302 'Города' является совершенно аналогичной той, которую я сформулировал. Только n<=1000.... Щас попробую ее решить...
|
|
|
| 20 Карелин Виталий Александрович, 26 марта 2009 г. 18:36:19 | |
|
Все, вроде понял, почему так. Сортировка.... Если засортировать все ребра в порядке увеличения, то не нужно каждый раз искать минимальное ребро за n^2, достаточно обратится к массиву ребер... Но для хранения всех ребер при n=8000 нужна уйма памяти, и, мне кажется, больше чем 16 Мб...
|
|
|
