SPOJ ADABLOOM — General Maximum Matching using Vertex Split

Revision en1, by HynDuf, 2020-11-21 08:03:07

Recently, I came across this problem: ADABLOOM. In short, Given an array $$$A$$$ of length $$$n$$$, the problem requires us to find the number of maximum matching in which each matching $$$(i,j)$$$ satisfies $$$A_i < (A_i \oplus A_j) < A_j$$$ (XOR operator).

I found a solution here. They simply doubled the graph to make the left and right side and then find the maximum matching in the bipartite graph, and divide by $$$2$$$ to get the answer.

I know that this algorithm won't work with general graph so I want to ask the proof of correctness of this algorithm and what properties that make this kind-of-general-matching problem solvable using this method. Thanks <3

Tags maximum matching, help, adabloom

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English HynDuf 2020-11-21 08:17:58 10
en1 English HynDuf 2020-11-21 08:03:07 825 Initial revision (published)