В стране 100 городов и 1000 дорог; каждая дорога соединяет ровно 2 города. Известно, что из любого города можно добраться в другой (возможно, через некоторые другие города) не больше, чем за 8 ч. Мужик на желтой «Калине» хочет объехать все города и вернуться в исходный город. За какое минимальное время он гарантированно может это сделать?
Подсказка
Для построение примеры выделите одну из вершин. А часть рёбер сделайте очень длинными.
Решение
Ответ: 99.8 часов.
Решение: Оценка. Граф городов и дорог не полный, значит, кратчайший путь между какими-то двумя городами проходит через какой-то город. Пусть, например, кратчайший путь от 
до 
проходит через 
. Тогда, цикл 
требует не более 
часов, так как переезд от к и все остальные переходы требуют не более 8 часов каждый.
Пример. Все города связаны с дорогами, требующими 4 часов каждая. Остальные города либо связаны дорогами, либо нет, чтобы общее число дорог равнялось 1000. Все дороги между ними требуют 8 часов. Легко видеть, что оценка достигается.