Задача: UVa :: 11183 — Teen Girl Squad.

Там есть обсужение: форум UVa

Это один и тот же алгоритм:)

Возьмем любую вершину и начнем строить путь от нее по самым дешевым ребрам (если исходящее ребро минимального веса будет не одно, подойдет любое). В ходе такого процесса мы или упремся в корень, либо зациклимся. В первом случае берем любую из вершин, которые не вошли в этот путь и повторяем все сначала с тем лишь исключением, что останавливаться будем, когда упремся в уже обработанную вершину. Во втором нужно сжать цикл и создать новую вершину с соответствующими весами входящих и исходящих из нее ребер и повторить процесс сначала.

Почему это O(n²)? Всего будет создано 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.