Design Space

The engineers from UFFS are studying the possibility of of building underground tunnels everywhere in the campus. The places where the entrances will be built, as always, were already chosen by MEC (Brazil's ministry of education), and the tunnels must least directly to one entrance to another. Since the budget was already done, these rules cannot be changed.

The original project was very well made, and there was a gallery between each pair of entrances, that were made in a way they would not cross, and the cost of these galleries was already paid. However, with the recent budget cuts, it is now necessary to chose only a subset of these galleries, without changing them, in a way that there is only one path between each pair of entrances.

The challenge now is to know the least and the largest cost possible, to fit in the new budget.