Help the engineer

An engineer working for a telecom company wants to design a cable network in a small nation. He can only bury the cables along main roads. Some paths are more expensive than others. It turns out that a previous employee of the company had already layed a network that is not efficient. In order to minimize costs, our engineer wants to optimize the network by removing some edges while keeping all points on the network connected.

For example, the network below can be optimized by removing the edge from 11 to 44: This saves a cost of 33.

The engineer is given this larger network to optimize. What is the total cost saved?

Details and assumtions

  • The network is represented in the text file is represented in an adjacency matrix representation. Basically, the cost from node xx to node yy is represented in the matrix AA as AxyA_{xy}(column xx, rowyy). Axy=0A_{xy}=0 if a path doesnt exist from xx to yy.

  • The example network in the picture above has the following adjacency matrix representation:


Problem Loading...

Note Loading...

Set Loading...