Лабораторная работа: Алгоритмы на графах

Составить программу на С++. Словесно подробно описать алгоритм решения задачи. Дополнительные требования находятся в прикреп.файле
В городе Энске находятся N предприятий, которые в течение нескольких лет пытались протянуть между собой электронные линии связи. Причем каждое предприятие действовало самостоятельно. Когда в 2002 году руководители предприятий собрались на Первой Энской конференции по информационным технологиям, выяснилось, что целый ряд соединений является избыточным. Действительно, если предприятие A имеет прямые линии к предприятиям B и C, а те в свою очередь - между собой, то одно из соединений AB, BC или AC можно удалить, не нарушая связи между тремя этими предприятиями. В целях экономии желательно удалить наиболее длинный кабель из трех. Требуется по имеющейся информации о соединениях между предприятиями выяснить, какие линии можно удалить без ущерба для связи так, чтобы длина удаленного кабеля была максимально возможной.