10369 - Arctic Network
You have a set of outposts, and you want to communicate all. You have 2 choices 1.- Via satellites 2.- Via transceivers And you have only S satelllites channels available
Given a set of terminals and number of satellites, you want to know the minimun range of the transceivers so that all stations are connected You assume the transceivers at the outposts must be identical
How many connections vis transceivers do you have?
You can use Kruskal algorithm, Minimum Spanning Forest. You have S satellites connection, and V stations, first you calculate the distance between all outposts, then you know you have V-S connections via transceivers. With kruskal algorithm you have to choose the minimum edges, so you only need to pick the maximum edge which belongs to the minimum spanning forest
or use Binary Search.
2 2 4 0 100 0 300 0 600 150 750 3 6 0 1 0 2 0 4 0 5 0 7 0 8