[Python]bit全探索 ABC190C

#ABC190C

$K$を筆頭に制約が狭いので、全探索の時間計算量を検討すると、$O(2^K(N+M+K))$で適合する。
bit全探索で $co[i]$ を皿 $i$ 置かれたボールの数として、実装する。

サンプルコード

n,m = list(map(int,input().split()))
ab = [list(map(int,input().split())) for _ in range(m)]
k = int(input())
cd = [list(map(int,input().split())) for _ in range(k)]

ans = 0
for bit in range(1<<k):
  co = [0]*(n+1)
  for i in range(k):
    if bit&(1<<i):
      co[cd[i][0]] += 1
    else:
      co[cd[i][1]] += 1
  anss = 0
  for a,b in ab:
    if co[a]>=1 and co[b]>=1:
      anss += 1
  ans = max(ans, anss)
print(ans)