Блог пользователя qwerty

Автор qwerty, история, 5 лет назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится