# PROBLEM LINKS

## DIFFICULTY

EASY

## PREREQUISITES

Graph, Tree, Kruskal’s Algorithm

## PROBLEM

You are given an undirected graph representing cities and roads in Byteland. Initially, there are no roads connecting the cities. Chef and other companies have proposed to build roads. Each road proposal also gives the cost of building the road. In other words, there are two types of road proposals: the ones proposed by Chef and the ones proposed by other companies. Choose a subset of the road proposals in such a way that for each two cities, there is exactly one path of roads between them, and the total cost of Chef’s chosen road proposals is maximized. If there are more than one way, choose the way where the total cost of all chosen road proposals is minimized.

## QUICK EXPLANATION

Use Kruskal’s Algorithm twice. First, consider each of the Chef’s road proposals in non-increasing order of cost and add each road if it connects two different tree of cities. Hence, we will have a maximum spanning forest of cities. Second, consider each of the other companies’ road proposals in non-decreasing order of cost and add each road if it connects two different tree of cities.

After all road proposals have been considered, if the cities are still not connected, the answer is “Impossible”.

## EXPLANATION

A graph where there is exactly one path between every two vertices is a tree. Essentially, the problem asks for a spanning tree of the graph which satisifies some constraints. We will use greedy approach to solve this problem.

The first constraint is that the total cost of Chef’s chosen road proposals is maximized. Therefore, we should first build a spanning forest considering only Chef’s road proposals. Use Kruskal’s Algorithm. Since we want to maximize the total cost, we should consider the road proposals in non-increasing order of cost, building a maximum spanning forest.

We can use Union-Find data structure to implement the Kruskal’s Algorithm. The pseudocode is as follows.

sort the Chef's road proposals in non-increasing order of cost total_chef = 0 for i = 0; i < M2; i++: (u, v, c) = chef_road_proposal[i] if u and v are in different components: merge u's and v's components total_chef = total_chef + c

After building the maximum spanning forest, there will be connected component(s) of the graph consisting of trees. The next step is to connect the components in the forest to form a single tree as required by the problem statement. We will use other companies’ road proposals to connect these trees. Since we want to minimize the total cost, we should consider the road proposals in non-decreasing order of cost.

sort the other companies' road proposals in non-decreasing order of cost total_others = 0 for i = 0; i < M1; i++: (u, v, c) = others_road_proposal[i] if u and v are in different components: merge u's and v's components total_others = total_others + c

The answer to this problem is (total_chef, total_chef + total_others). However, if after the whole steps the cities are still not connected, then the answer is “Impossible”.

Now, you may wonder how to handle Chef’s road proposals with equal costs. What is the tie-breaker method? The choice for Chef’s road proposals with equal costs seems to affect the choice for other companies’ road proposals too. We will prove that this is not important; we can sort road proposals with equal costs in any order.

**Theorem**. The set of (set of cities which forms a single component), after building the maximum spanning forest considering Chef’s road proposals only, is always the same no matter how you handle ties between road proposals with equal costs.

For example, let N=6 and a maximum spanning forest divides the cities into three components: {3, 4}, {1}, {2, 5, 6}. Then, any other ways of handling the road proposals with equal costs will always gives {{3, 4}, {1}, {2, 5, 6}}.

**Proof**. The proof is by contradiction. Suppose there are two ways which gives two different configurations of components. Then, in the first configuration, there will be a Chef’s road proposal which connects two cities of different components (otherwise there will be only one possible configuration). However, this is not possible: this road proposal should have been chosen at the first place in Kruskal’s Algorithm during the first step of the solution. Therefore, there is exactly one configuration of components as the result of building the maximum spanning forest.

Now that the theorem is proved, the answer only depends on the tie-breaker method during the Kruskal’s Algorithm in the second step, i.e., for other companies’ road proposals. However, this is also not important because we only care about the total cost. Conclusion: we can handle all road proposals with equal costs in any way we want.

The time complexity of this solution is O(M1 log M1 + M2 log M2) + (time complexity of the Union-Find data structure). With union by rank and path compression techniques, we can achieve time complexity of O(M1 log M1 + M2 log M2 + N).

## SETTER’S SOLUTION

Can be found here

## TESTER’S SOLUTION

Can be found here