CSAcademy 23 E. No Prime Sum ( Bipartite Matching, Minimum Vertex Cover )

題意：
給 N 個相異正整數，問最少要移除幾個數字，能使任意兩個數字的和不為質數。輸出方案。

限制：
2≤N≤2000
The elements of S are distinct integers between 1 and 10^5

解法：
首先顯然偶數+偶數以及奇數+奇數的情形一定不會產生質數。將奇數劃分為集合 L，偶數劃分為集合 R，對兩兩會形成質數的點對連邊，問題便等價於「移除最少的點，使得這個二分圖上不存在邊」。賽中只有想到這裡，用亂數之類的貪心優先拔取度數最大，顯然慘掉。
這個問題是經典的 MVC ( Minimum Vertex Cover )，Kőnig's theorem 表示這個問題可以等價於最大匹配。至於構造方法看了維基百科還是看不懂，所以參考這裡。簡單來說，先用類如 Kuhn's Algorithm 等等得出二分圖最大匹配後，考慮枚舉所有未拜訪且不屬於任何最大匹配邊的屬於 L 集合的節點進行 DFS，最大匹配邊是由 R 指向 L 的有向邊，而其他的邊由 L 指向 R。做完 DFS 後，屬於 L 集合的節點中未拜訪的，以及屬於 R 集合的節點中被拜訪的，這個聯集即是所求的 MVC。至於證明我也還不是很懂，可以參照上面連結，有空再理解。

時間 / 空間複雜度：
O( V * E )

np = [ False for i in range( int( 2e5 + 1 ) ) ]
for i in range( 2, len( np ), 1 ):
  if np[ i ]: continue
  for j in range( i + i, len( np ), i ):
    np[ j ] = True

N = int( input() )
S = list( map( int, input().split() ) )

L = []
R = []
for i in range( N ):
  if S[ i ] & 1:
    L.append( S[ i ] )
  else:
    R.append( S[ i ] )
    
adj = [ [] for i in range( len( L ) ) ]
for i in range( len( L ) ):
  for j in range( len( R ) ):
    if not np[ L[ i ] + R[ j ] ]:
      adj[ i ].append( j )
      
bf = [ -1 for i in range( len( R ) ) ]
gf = [ -1 for i in range( len( L ) ) ]
def find_mate( u, vis = None ):
  global bf
  global gf
  if vis == None:
    vis = [ False for i in range( len( R ) ) ]
  for v in adj[ u ]:
    if vis[ v ]: continue
    vis[ v ] = True
    if bf[ v ] == -1 or find_mate( bf[ v ], vis ):
      bf[ v ] = u
      gf[ u ] = v
      return True
  return False

match_cnt = 0
for i in range( len( L ) ):
  if gf[ i ] != -1: continue
  match_cnt += find_mate( i )
  
print( match_cnt )

vis_L = [ False for i in range( len( L ) ) ]
vis_R = [ False for i in range( len( R ) ) ]
def dfs_alternate( u, nowR ):
  global vis_L
  global vis_R
  if not nowR:
    for v in adj[ u ]:
      if vis_R[ v ]: continue
      if bf[ v ] == u: continue
      vis_R[ v ] = True
      dfs_alternate( v, True )
  else:
    if bf[ u ] == -1: return
    vis_L[ bf[ u ] ] = True
    dfs_alternate( bf[ u ], False )
for i in range( len( L ) ):
  if gf[ i ] != -1: continue
  if vis_L[ i ]: continue
  vis_L[ i ] = True
  dfs_alternate( i, False )

ans = []
for i in range( len( L ) ):
  if vis_L[ i ]: continue
  ans.append( L[ i ] )
for i in range( len( R ) ):
  if not vis_R[ i ]: continue
  ans.append( R[ i ] )
print( *ans )