Задача 107
Наименьшая сеть

Представленная ниже ненаправленная сеть состоит из семи вершин и двенадцати граней, общий вес которых равен 243.


Ту же сеть можно представить в виде матрицы, как это показано ниже.

    ABCDEFG
A-161221---
B16--1720--
C12--28-31-
D211728-181923
E-20-18--11
F--3119--27
G---231127-

Однако, данную сеть можно оптимизировать, убрав из нее несколько граней таким образом, чтобы все вершины сети оставались соединенными в одну сеть. Наиболее экономичный вариант такой сети показан ниже. Общий вес ее граней равен 93, что на 243 − 93 = 150 меньше, чем у исходной сети.


В текстовом файле network.txt (щелкнув правой кнопкой мыши, выберите 'Save Link/Target As...') размером 6KБ в виде матрицы задана сеть, у которой сорок вершин. Найдите наибольший выигрыш в суммарном весе граней, который можно достигнуть, удаляя избыточные грани так, чтобы в то же время все узлы оставались соединенными в одну сеть.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net