Блог пользователя speedster

Автор speedster, 9 лет назад, По-английски

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 .

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.