Верхняя граница через группы

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

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 2. Если путь покинул группу взаимной достижимости и затем вернулся, все промежуточные вершины взаимно достижимы с этой группой и должны входить в неё. Поэтому разные группы вдоль пути не повторяются. Между группами получается конечная схема без циклов. Вес группы — число её вершин; максимальное число разных значений не больше наибольшей суммы весов по цепочке групп.

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу