flash_7's blog

A Bipartite Matching Problem (UVa 11419 — SAM I AM)
By flash_7, history, 9 years ago, In English

I'm stuck with this problem and can't figure out how to proceed.Can anyone give me some hints how can i solve it using BPM?

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Think of a graph with nodes corresponding to rows on the left and nodes corresponding co columns on the right.

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

Search about minimum vertex cover on bipartite, König's theorem.

Interesting part of this problem is that you shouldn't output the cardinality of MVC, but you should be able to recover the solution as well. Proof of König's theorem on Wikipedia already provides an efficient algorithm for retrieving that.

→ Reply