Submission #70172971

---

Source Code Expand

"""
<方針>
- `N` は小さいが、`M` は bit 全探索できるほど小さくない。
- そこでまず、どのような黒白のパターンがあるかを全探索する。
- その上で、それを成立させられるように辺を切ってみれば良い。
- 一番辺を切った回数が少ないところを選べば良い。
- 全体として、`O(2^N・M)` となる。
"""

# 双方向グラフ構築。
N, M = map(int, input().split())
E = [[False]*N for _ in range(N)]
for _ in range(M):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  E[u][v] = True
  E[v][u] = True

# 最小削除数
ans = float("inf")

# 黒白全パターン
for b in range(1<<N):
  
  # 黒いところを保存する。
  black = [False]*N
  for bit in range(N):
    if(b>>bit & 1):
      black[bit] = True
  
  # 削除回数
  tmp = 0
  for u in range(N):
    for v in range(N):
      # 辺がつながっている & 色が同じ
      if(E[u][v] and (black[u] == black[v])):
        tmp += 1
  
  # 双方向でカウントしたので、半分にしておく。
  tmp //= 2
  
  # 更新する
  ans = min(ans, tmp)

# 出力
print(ans)

Submission Info

Judge Result