Replay of BSMRSTU Home Quarantine Contest — 3

Правка en1, от 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский qwerty 2020-05-12 06:06:46 793 Initial revision (published)