GCJ 2017 Qual D. Fashion Show ( Bipartite Matching )

Dashboard - Qualification Round 2017 - Google Code Jam

題意：
給 N * N 的棋盤，以及一些士兵。士兵有三種 : { 'x', '+', 'o' }，若沒有士兵用 '.' 描述。一個格子至多一個士兵。士兵配置的規則如下：
1. 任意兩個在同個水平或鉛直線上的士兵，必須有其中一個是 '+'。
2. 任意兩個在同個正斜線上的士兵，必須有其中一個是 'x'。
你可以進行兩種操作：
1. 將已存在的士兵由 'x' 或 '+' 升格為 'o'。
2. 將任意一種士兵配置在空的格子上。
問最佳操作，最大化棋盤的分數。
棋盤的分數是 'x' 的數量 + '+' 的數量 + 'o' 的兩倍數量。

制約：
1 ≤ T ≤ 100.
1 ≤ N ≤ 100.
1 ≤ Ci ≤ N, for all i.
0 ≤ M ≤ N^2.

解法：
首先將 'o' 視為 '+' 和 'x' 的重疊。
接著考慮將這個棋盤分為兩個獨立的棋盤，一個只有 '+'，一個只有 'x'。
換個說法，題意表示任意兩個 '+' 不能同時出現在一個正斜線上，同時，任意兩個 'x' 不能同時出現在一個水平或鉛直線上。由於問題是獨立的，只要分開求最大化即可。這兩個都是經典問題，前者是最大化 bishop 在棋盤上不衝突的數量，後者是最大化 rook 在棋盤上不衝突的數量。後者只要輕鬆貪心即可，因為一個 rook 不多不少只會剛好佔據一個鉛直線和一個水平線，怎麼做都會有最大數量 N。前者可以用二分圖匹配解決，由於一個配置 ( x, y ) 可以用兩方向的各一個唯一確定的正斜線描述，以正斜線為節點，左上至右下為一邊的集合，右上至左下為另一邊的集合，有交點的節點間連邊，剛好帶有二分圖的特性。
話說我不太確定這個匹配算法的複雜度究竟是...? 看起來至少平均情況大約 N^3。
另外，雖然跟這題沒關係，不過原來在 N * N 的棋盤上任意配置 bishop 時，最佳配置是這樣，而且最大匹配數是 N - 2。

時間 / 空間複雜度：
O( N^3 ) / O( N^2 )

def match( u, edge, gf, bf, vis = None ):
  if vis == None:
    vis = [ False for i in range( len( edge ) ) ]
  for v in edge[ u ]:
    if vis[ v ]: continue
    vis[ v ] = True
    if bf[ v ] == -1 or match( bf[ v ], edge, gf, bf, vis ):
      bf[ v ] = u
      gf[ u ] = v
      return True
  return False

T = int( input() )
for ti in range( 1, T + 1, 1 ):
  N, M = map( int, input().split() )
  G = [ [ '.' for i in range( N ) ] for j in range( N ) ] # original graph
  nG = [ [ '.' for i in range( N ) ] for j in range( N ) ] # modifying graph
  for mi in range( M ):
    f, x, y = input().split()
    x, y = int( x ) - 1, int( y ) - 1
    x, y = map( int, [ x, y ] )
    G[ x ][ y ], nG[ x ][ y ] = f, f
  # solve rook
  vis_x = [ False for i in range( N ) ]
  vis_y = [ False for i in range( N ) ]
  for i in range( N ):
    for j in range( N ):
      if G[ i ][ j ] == 'x' or G[ i ][ j ] == 'o':
        vis_x[ i ], vis_y[ j ] = True, True
  for i in range( N ):
    for j in range( N ):
      if vis_x[ i ] or vis_y[ j ]: continue
      vis_x[ i ], vis_y[ j ] = True, True
      if nG[ i ][ j ] == '.':
        nG[ i ][ j ] = 'x'
      elif nG[ i ][ j ] == '+':
        nG[ i ][ j ] = 'o'
  # rook solved
  # solve bishop with bipartite matching
  used_4 = [ False for i in range( 2 * N - 1 ) ] # top-left to bottom-right
  used_6 = [ False for i in range( 2 * N - 1 ) ] # top-right to bottom-left
  for i in range( N ):
    for j in range( N ):
      if nG[ i ][ j ] == '+' or nG[ i ][ j ] == 'o':
        used_4[ N - 1 + j - i ], used_6[ i + j ] = True, True
  edge = [ [] for i in range( 2 * N - 1 ) ]
  for i in range( 2 * N - 1 ):
    if used_4[ i ]: continue
    for j in range( 2 * N - 1 ):
      if used_6[ j ]: continue
      yy = i + j - ( N - 1 )
      if yy & 1: continue
      x, y = j - yy // 2, yy // 2 # intersection
      if not ( 0 <= x and x < N and 0 <= y and y < N ): continue
      edge[ i ].append( j )
  gf = [ -1 for i in range( 2 * N - 1 ) ]
  bf = [ -1 for i in range( 2 * N - 1 ) ]
  for i in range( 2 * N - 1 ):
    match( i, edge, gf, bf )
  for i in range( 2 * N - 1 ):
    if gf[ i ] == -1: continue
    y = i + gf[ i ] - ( N - 1 ) >> 1
    x = gf[ i ] - y
    if nG[ x ][ y ] == '.':
      nG[ x ][ y ] = '+'
    elif nG[ x ][ y ] == 'x':
      nG[ x ][ y ] = 'o'
  # evaluate score and print difference
  scr, diff = 0, 0
  for i in range( N ):
    for j in range( N ):
      diff += G[ i ][ j ] != nG[ i ][ j ]
      if nG[ i ][ j ] == '+' or nG[ i ][ j ] == 'x':
        scr += 1
      elif nG[ i ][ j ] == 'o':
        scr += 2
  print( "Case #%d: %d %d" % ( ti, scr, diff ) )
  for i in range( N ):
    for j in range( N ):
      if G[ i ][ j ] == nG[ i ][ j ]: continue
      print( "%c %d %d" % ( nG[ i ][ j ], i + 1, j + 1 ) )