All problems

Rail Regions

Medium · minimum spanning tree

A railway has n stations, numbered 0 to n - 1. Some track is already laid: each entry [a, b] in built is a track between stations a and b that works in both directions and is free to use.

Two stations belong to the same region if trains can get from one to the other, directly or through other stations. A station with no track is a region of its own.

Every region needs its own control room, and the railway can afford only k of them. It may buy new tracks from the list offers: each entry [a, b, cost] is a track between stations a and b that costs cost to build, and you may buy any of them, in any combination.

Return the smallest total cost of new tracks that leaves at most k regions. If the stations already form at most k regions, return 0. If no choice of tracks can bring the number of regions down to k, return -1.

Several tracks may join the same two stations, and costs may be 0.

Examples

Example 1

Input: n = 6, built = [[0, 1], [2, 3]], offers = [[1, 2, 5], [3, 4, 2], [4, 5, 7], [0, 5, 4]], k = 2

Output: 6

The built track leaves four regions: {0, 1}, {2, 3}, {4} and {5}. Buy 3-4 (2) and then 0-5 (4) to leave two regions: 2 + 4 = 6. The track 1-2 would cost more and is not needed.

Example 2

Input: n = 4, built = [[0, 1], [1, 2], [2, 3]], offers = [[0, 3, 9]], k = 1

Output: 0

One region already, so nothing needs to be bought.

Example 3

Input: n = 5, built = [], offers = [[0, 1, 3], [1, 2, 3]], k = 2

Output: -1

The two tracks can only bring five regions down to three.

Constraints