Replay of BSMRSTU Home Quarantine Contest — 3

Revision en1, by qwerty, 2020-05-12 06:06:46

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English qwerty 2020-05-12 06:06:46 793 Initial revision (published)