UVa 10369

From Algorithmist
Jump to navigation Jump to search

10369 - Arctic Network[edit]


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 4
0 100
0 300
0 600
150 750
3 6
0 1
0 2
0 4
0 5
0 7
0 8