Остовное дерево с заданным весом

Правка ru1, от Dword, 2018-10-23 18:13:37

Приветствую всех. Хотел бы узнать, как решить одну задачу (уже не помню откуда). Дан неориентированный 0-1 граф с n вершинами и m ребрами и число k. Необходимо найти остовное дерево с суммарным весом ровно k (или сообщить, что такого не существует). Ограничения: 1 <= n, k <= 10^5, 1 <= m <= 2 * 10^5. Время 2 сек, память 256 Мб. У кого какие идеи?

Теги графы, деревья, остовное_дерево

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский Dword 2018-10-23 18:13:37 409 Первая редакция (опубликовано)