We can think of countries as minimum-spanning trees (MST), cities as nodes, and roads as edges in the graph. Then we can rephrase the problem as building disconnected MST using nodes and in a way so that the maximum cost among minimum spanning trees is the minimum possible.
Iterative Solution:
At first, we will pre-compute and store the cost of MST for every possible subset of cities if these cities are connected otherwise the cost will be stored as . Let’s define as the cost of the minimum spanning tree of the subset of cities.
Finally, we will use dynamic programming with bitmask
to distribute the cities among countries. Let’s suppose, denotes the minimized maximum cost to distribute a subset of cities among first countries. Now, for the country, we will enumerate all sub-masks of mask . Then, we will calculate the minimum possible maximum cost for the first countries as follows:
Time Complexity:
Overall time complexity is .
We will require to iterate through all masks with their sub-masks. And we will also require to pre-compute the cost of MST for all possible subsets of cities.
Memory Complexity:
Overall memory complexity is .