speedster's blog

Bipartite matching
By speedster, 10 years ago, In English

Hello , I was trying to solve O2J ladder for bipartite matching but got stuck in HERE I know this is bipartite matching but I am unable to figure out what would the vertices in set1 represent and similarly what would the vertices in set2 represent . A hint would be appreciated .

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

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

The opaque rooms divide the board into vertical and horizontal segments. Inside of those segments, you can place only one fighter, and each cell of the board will belong to exactly one horizontal segment and one vertical segment. So you can build a bipartite graph where the left part are horizontal segments, the right part are vertical segments and if a cell belongs to horizontal segment h and vertical segment v, there's an edge [u, v] with capacity 1. The answer will be the max flow of that graph.

You must be careful with the implementation though, because it might give you TLE.

→ Reply