# GCJ 2017 Qual D. Fashion Show ( Bipartite Matching )

Dashboard - Qualification Round 2017 - Google Code Jam

1. 任意兩個在同個水平或鉛直線上的士兵，必須有其中一個是 '+'。
2. 任意兩個在同個正斜線上的士兵，必須有其中一個是 'x'。

1. 將已存在的士兵由 'x' 或 '+' 升格為 'o'。
2. 將任意一種士兵配置在空的格子上。

1 ≤ T ≤ 100.
1 ≤ N ≤ 100.
1 ≤ Ci ≤ N, for all i.
0 ≤ M ≤ 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 ) )
```