Arctic Network
Solution Sketch
Build a MST using Kruskal algorithm.
The curcial observation to solving this problem is $s$ satellites can save you $s - 1$ edges in the MST!
So, while you are using Kruskal algorithm to build the MST, you also need to keep a counter of how many edges have been added into the MST. If $p - 1 - cnt = s - 1$, which means total edges in MST $p - 1$, minus $cnt$ (number of edges in MST currently), equals to the edges that can be saved $s - 1$, we can terminate the MST algorithm and output the distance of the last edge that was added.
AC Code
|
|