pks18's blog

By pks18, history, 3 years ago, In English

While trying the problem Tree Matching, I figured out that onw way to solve the problem could be to use network flow by adding a source and sink after splitting the tree into two partite. Otherwise, another way could be to use Hopcroft-Karp Algorithm to find the maximum matching.

There is no article written on this topic on CP Algorithms website. And on other webisites, I didn't find a implementation as clear and general as they are on CP Algorithms.

It would be great if some clean and documented implementation of this code could be shared (may or may not be a blogpost on Codeforces).

Thanks in advance!

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

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

This implementation is not the most documented example (the only documentation present here comes from the variable names), but should be easy to follow if you know the pseudocode of the algorithm.