Minimum Cost to Connect Network

Hard
0/120
0 upvote
Asked in company
Amazon

Problem statement

You are the network administrator for a campus with n buildings. A set of cables originally connected all buildings, forming a single connected network. Unfortunately, due to some damage, some of these cables are now broken.


You are given:

  • n: The number of buildings (nodes), numbered 1 to n.
  • edges: A list of all cables that are currently working.
  • broken_edges: A separate list of the broken cables, along with the cost to repair each one.


Your task is to determine the minimum total cost to repair a selection of broken cables so that all n buildings are once again part of a single, fully connected network.


If it's impossible to connect all buildings even after repairing all broken cables, you should report it.


Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer n, the number of buildings.

The second line contains an integer e, the number of working edges.

The next e lines each contain two space-separated integers, u and v, representing a working cable between buildings u and v.

The next line contains an integer b, the number of broken edges.

The next b lines each contain three space-separated integers, u, v, and cost, representing a broken cable between u and v with its repair cost.


Output Format: 
Your function should return a single integer representing the minimum cost to reconnect the network.

If it's impossible to reconnect the network, your function should return -1.

The runner code will handle printing the returned value.


Notes: 
This problem can be modeled as finding a Minimum Spanning Tree (MST) on a graph.
Sample Input 1:
4
2
1 2
3 4
3
1 3 10
2 3 20
1 4 100


Sample Output 1:
10


Explanation for Sample 1:
Initially, working edges (1,2) and (3,4) form two separate components: {1, 2} and {3, 4}.
The broken edges are (1,3) with cost 10, (2,3) with cost 20, and (1,4) with cost 100.
To connect the two components, we greedily pick the cheapest broken edge: (1,3) with cost 10.
Repairing this edge connects components {1,2} and {3,4} into a single network {1,2,3,4}.
The minimum cost is 10.


Expected Time Complexity:
The expected time complexity is O(E+BlogB).


Constraints:
1 <= n <= 1000
0 <= e, b <= 10^5
1 <= u, v <= n
1 <= cost <= 1000
Time Limit: 1 sec
Approaches (1)
union find
Time Complexity
Space Complexity
Code Solution
(100% EXP penalty)
Minimum Cost to Connect Network
Full screen
Console