Блог пользователя consoleapplication1

Автор consoleapplication1, 11 лет назад, По-русски

Добрый день, есть задача. Дан неориентированный невзвешенный граф, состоящий из N<50 вершин и M<100 ребер. К вершин (K<=N) имеют некую метку, нужно соединить эти К вершин минимальным количеством ребер (то есть некое подобие остова). Есть ли что-то лучше перебора? Задача из реального мира, интересует точное решение

upd нужно выбрать путь по существующим ребрам, новые проводить нельзя

Полный текст и комментарии »

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится