qwerty's blog

Replay of BSMRSTU Home Quarantine Contest — 3
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?

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not sure about the solution. I am sharing the first thing that came to my mind. Let me know if there's any flaw or if I missed anything.

Since we can generate MST by sorting all their edges according to their weight we can use this algorithm to solve this problem.

There are two types of colored nodes in this graph. So we can divide these edges according to their color. Black edges go to a vector, White edges go to another vector. Now let's sort all the black and white edges according to their weight separately.

Now, as we need exactly k edges: we will start constructing the tree using only white edges until we get to use the total k white edges. After using a total of k white edges in that tree then we will start using all the black edges until the tree is built fully.

Now when we will be unable to construct a tree with exactly k white edges? It's yours to find out. ;)

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Try this:
    $$$N$$$ = 4, $$$k$$$ = 1 

    1 -> 2, wt = 100, col = white 
2 -> 3, wt = 1, col = black 
2 -> 4, wt = 1, col = black
3 -> 4, wt = 2, col = white


    MST can be formed with weight 102 while according to your solution you will choose white edge of weight 2 and won't be able to make a tree.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh damn. :(

      Thanks for pointing out the mistake. :D

      → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Try this.

→ Reply
»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

This is a pretty well-known problem actually. I have solved it using Aliens trick during the contest. The exact problem has already been discussed here.

→ Reply