1
$\begingroup$

There are n cities and m possible roads and k temples. The cost of each road is given. Build roads with minimum cost such that each city has access to at least 1 temple.

Note that there can be multiple roads(edges) between two cities and each temple is inside a city.

My attempt : I tried running Kruskal's Algorithm of the graph and then sort edges in descending order and then remove them one by one if the graph still satisfies the condition. I don't know this algorithm is correct or not.

I found this question in an algorithm book.

$\endgroup$
1
  • 1
    $\begingroup$ Please credit the original source of this problem. $\endgroup$ Nov 26 '21 at 16:06
1
$\begingroup$

Add a new vertex $v$ to the graph. For every city node $u$ that contains a temple, add a $0$ weighted edge $(v,u)$ to the graph. Let the new graph be $G'$. Find the minimum spanning tree of $G'$. It would give the minimum cost of constructing roads such that every city has access to at least one temple.

Please try to prove correctness by yourself. Let me know if it works.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.