Губернатор собирается сэкономить на ремонте дорог, соединяющих населённые пункты региона. Схема дорог с их протяжённостью в километрах изображена ниже.

Решение губернатора оказалось радикальным – закрыть на неопределённый период "лишние" дороги (и, соответственно, сэкономить на их ремонте), сохраняя связность между населёнными пунктами. Он приходит к следующей схеме:

Да, добираться от одного пункта до другого стало неудобно. Скажем, если раньше люди могли сразу доехать из C в D, то теперь им придётся ехать сперва до B, потом до E и только в конце – до D. Неудобство с A и C мы даже не рассматриваем (транспортный поток между этими пунктами якобы и так был мал). Зато какая выгода! Теперь нам придётся ремонтировать дороги общей протяжённостью 37 + 11 + 12 + 9 + 17 = 86 км, тогда как до закрытия речь шла о 163 км.

Если экономить, то до конца!

Однако в данной ситуации появляется консультант-математик, который применяет алгоритм Краскала и указывает губернатору на выгодное развитие его идеи. Он предлагает ему следующую схему:

Протяжённость данной схемы составит всего 53 км вместо 86 (и это минимальная возможность). Таким образом, губернатор сэкономит на ремонте ещё 86 - 53 = 33 км дорог, что соответствует 999 млн руб. дополнительной прибыли (приблизительная стоимость одного километра асфальтового покрытия – 33 млн).