qwerty's blog

By qwerty, history, 5 years ago, In English

Can someone help in the following problem? (Source)

You are given an bidirectional weighted graph with N nodes and M edges. Every edge is colored with black or white color (0 means black and 1 means white). You are given also an integer K. You have to find the minimum spanning tree such that there is exactly K white edges in the tree or identify there is no solution.

The graph is connected and there can be multiple edges between two nodes.

I managed to observe that bridges need to be included in any MST, so we may decrease K by the no. of white bridges. Can someone provide a sketch of the whole solution?

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it