Low Cost Road Network - new problem 260

This is a problem of medium difficulty so should attract a reasonable number of solvers. The basic idea is to minimise the cost of a road network. There is a recognised algorithm which could be used but it is fairly easy to deduce what needs to be done without knowing the algorithm. However, without a good algorithm it is unlikely that users will be able to find a solution for a large data set. The example given is small and could be solved by hand.

It might be better to return to this paragraph after reading the draft problem description. I have experimented with a variety of data sets for this problem. It soon became clear that a completely random data set is both unrealistic and makes it easier to solve the problem with a poor algorithm. I have written a routine which generates data randomly but with realistic values. For example, the costs of building a road between two villages are likely to be smaller if the villages are closer together. For the actual problem I am anticipating between 30 to 40 villages and a list of about 300 submitted road costs (not including the original submissions). These numbers can easily be increased if necessary. With 100 villages and 1000 road costs the generation and checking time was about 1 second.

The following is a draft problem description:

The land of Erewhon is very mountainous and travel between villages is possible only by following narrow mule paths. This means that trade between the villages is very difficult. The king decided to change that by linking the villages with simple roads that would allow the passage of a donkey pulling a cart. This would require the building of a number of bridges as well as preparing a solid bed for the road. To keep costs as low as possible the king decided to link all of the villages by a single continuous road. He drew up specifications for the quality of the road and got his builders to estimate the cost. The cost was rather more than he had expected. After some thought he decided that it was not necessary to have one continuous road. Any system of roads that made it possible to travel between any pair of villages would be acceptable. He also decided to invite all of the builders in the kingdom to submit costs for potential roads which would meet his specifications. The submitted cost could relate to a road link between any pair of villages in the kingdom.

The king was very pleased with the response to this invitation. He soon had a large number of costs for proposed roads. The problem now is to choose the set of roads which will cost the least. You will need to refer to the example below to fully understand what is required. The first line has a single integer N which is the number of villages. The initially proposed continuous road would need N-1 sections to run through all of the villages. The second line contains the initial N-1 costs for these road sections. For convenience we will number the villages 0, 1, 2, ..., N-1. So the proposed cost of building a road between villages 0 and 1 is 33993 silver pieces; the cost for the road between villages 1 and 2 is 81906 silver pieces and so on. The total proposed cost is 260009 silver piesces.

The next line of data contains a single integer M. This is the number of additional road costings which the king has now collected. (Note that these do not include the costings already given) M lines of data follow this. Each line contains three integers. The first two are the numbers of the villages to be linked and the third is the proposed cost. You now need to consider all proposed roads (including the initial N-1 sections). Where several costings have been given for a road between the same pair of villages, only the cheapest (if any) is likely to be chosen. You need to find the cheapest network which connects all of the villages and then work out how much cheaper this is than the cost of the original proposed road. It is this cost saving which is required for the answer.

Using the example below the cheapest network contains the following roads, with costs in brackets. 0-1 (33993), 0-3 (51594), 2-3 (15767), 2-4 (32584), 4-6(34108) and 5-6 (32865). These have a total cost of 200911, giving a cost saving of 59098 silver pieces.

Example:

input:
7
33993 81906 15767 34018 61460 32865
20
2 6 44915
4 0 91710
0 3 51594
4 2 32584
6 4 34108
4 5 58757
2 1 69940
6 5 33320
6 4 37759
5 6 34478
0 6 75539
5 4 59941
4 0 92877
0 5 62171
0 6 68991
3 6 40877
0 5 59027
2 6 51077
3 6 40683
3 2 17229

answer:
59098

Rodion, Hi.

In keeping with the rest of your site I am more than happy that the problem should have the name of the algorithm that is relevant to its solution. You may also wish to provide a description of it, or simply direct users to a suitable online reference.

Having read your comments, if you want to replace my problem entirely with one of your own devising I would not be offended. Please feel free to make any changes that you see fit; or even replace the problem.

I have sent you an e-mail with my setter/checker in case you decide to make use of it.

Rodion,

I have done several tests and the problem seems to be working as intended.

Thanks, Clive