Недавно встретил данную задачу для ограничений N<=100, M<=10000. Первая мысль была минкост, но он будет очень долго работать, так как сложность минкоста О(N^3*M). Подскажите пожалуйста, как решить заданную задачу за подходящее время (1-3 сек).
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3947 |
2 | jiangly | 3734 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | ecnerwala | 3581 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | ksun48 | 3479 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 162 |
2 | maomao90 | 160 |
3 | nor | 156 |
4 | cry | 155 |
4 | adamant | 155 |
4 | atcoder_official | 155 |
4 | -is-this-fft- | 155 |
8 | maroonrk | 153 |
9 | SecondThread | 147 |
10 | Petr | 146 |
Недавно встретил данную задачу для ограничений N<=100, M<=10000. Первая мысль была минкост, но он будет очень долго работать, так как сложность минкоста О(N^3*M). Подскажите пожалуйста, как решить заданную задачу за подходящее время (1-3 сек).
Название |
---|
The Directed Minimum Spanning Tree Problem?
Оно, спасибо!
Спасибо! Может кто-то подкинет задачку из онлайн-джадж на эту тему?
Задача: UVa :: 11183 — Teen Girl Squad.
Там есть обсужение: форум UVa
Алгоритм двух китайцев, оно?
Оно! Но выше написан, как по мне, легче алгоритм.
Это один и тот же алгоритм:)
так там с циклов нужно ребра удалять, а там как то строить конденсацию.
Третий пункт — чем тебе не конденсация? Ну и в начале, как бы, ссылаются на алгоритм Чу и Лю.
Если уж зашел разговор на эту тему — Тарьян давным-давно придумал, как это за O(n2) без тяжеловесных структур данных делать. Идея — будем стягивать циклы в вершину не пачками, а по одному, и использовать матрицу смежности.
Можно более подробно?
Возьмем любую вершину и начнем строить путь от нее по самым дешевым ребрам (если исходящее ребро минимального веса будет не одно, подойдет любое). В ходе такого процесса мы или упремся в корень, либо зациклимся. В первом случае берем любую из вершин, которые не вошли в этот путь и повторяем все сначала с тем лишь исключением, что останавливаться будем, когда упремся в уже обработанную вершину. Во втором нужно сжать цикл и создать новую вершину с соответствующими весами входящих и исходящих из нее ребер и повторить процесс сначала.
Почему это O(n2)? Всего будет создано O(n) вершин. Каждую вершину мы обработает единожды. Для каждой мы сделаем O(n) операций просмотра смежных ребер для выбора минимального исходящего. Этого же количества для каждой вершины, в случае конденсации, хватит, чтобы построить ребра для новой вершины.
Замечу, что здесь я строил дерево, ребра которого направлены к корню, а не от корня, но это не принципиально.
Кажется, в статье "Finding Optimum Branchings", Networks, v.7, 1977, pp. 25–35. все это дело описано, но я мог что-то забыть. Еще отмечу, что иногда ищут branchings, иногда — arborescence, иногда — r-arborescence. Первое — ориентированный лес, второе — дерево с произвольным корнем, а последнее — дерево с фиксированным корнем. Все они сводятся друг к другу построением O(n + m) дополниткльных вершин и ребер, но новый вес ребра, в случае конденсации, в каждом случае может отличаться. В случае r-arborescence для выходящего ребра (u, v) он будет равен c(u, v) - c(u, w), где c(u, w) минимально при фиксированном u.