Одеревенение (ОКД НТИ 17/18 :: ИЭС)

Легенда

У вас имеется электросеть, в которой каждый узел может быть генератором или потребителем, в зависимости только от его желания.

Сеть состоит из 20 узлов и 23 линий между ними, сеть связна. Для каждого узла известна потребляемый(генерируемый) ток. Сумма потребления и генерации в системе, естественно, равна нулю. Для каждой линии известно её электрическое сопротивление.

Сеть немного избыточна: линий в ней больше, чем минимально необходимо для эффективного снабжения потребителей.

Вам нужно написать программу, выбирающую линии, которые необходимо отключить, с тем, чтобы:

1. Сеть была связной — существовал путь от любого узла к любому другому.
2. Сеть была минимальной — ещё одно отключение любой линии нарушит связность.
   
3. Электрические потери в сети были бы минимальными.

Видео-разбор