問題
N 頂点 M 辺の無向グラフで最小頂点被覆。NP 困難なので 2-近似と局所探索を実装、より小さい方を出力。
制約
$2 \le N \le 1000$
$1 \le M \le 5000$
T = 1 秒
連結とは限らない
入出力例
入力例 1
6 7 1
1 2
1 3
2 4
3 4
3 5
4 6
5 6出力例 1
3ヒント (段階的開示)
ヒント1: 方向性
2-近似: 最大マッチングの両端点。局所探索: ランダム除去 + 補修で改善。
ヒント2: アプローチ
局所探索: 頂点を1つ除去 → 未被覆辺の他端点を追加 → 改善判定。
ヒント3: 誘導
time.time() で時間管理、time_limit*0.9 で探索終了。
模範解答 (Python)
import sys
import random
import time
input = sys.stdin.readline
def solve():
N, M, T = map(int, input().split())
edges = []
adj = [[] for _ in range(N + 1)]
for _ in range(M):
u, v = map(int, input().split())
edges.append((u, v))
adj[u].append(v); adj[v].append(u)
def is_cover(cover):
return all(u in cover or v in cover for u, v in edges)
def two_approx():
matched = set()
cover = set()
for u, v in edges:
if u not in matched and v not in matched:
matched.add(u); matched.add(v)
cover.add(u); cover.add(v)
return cover
def local_search(init_cover, time_limit):
cover = set(init_cover)
best = set(cover)
start = time.time()
while time.time() - start < time_limit:
if not cover:
break
v = random.choice(list(cover))
cover.remove(v)
uncovered = [(u, w) for u, w in edges
if (u == v or w == v) and u not in cover and w not in cover]
if uncovered:
for u, w in uncovered:
other = w if u == v else u
cover.add(other)
if len(cover) >= len(best):
cover.add(v)
for u, w in uncovered:
other = w if u == v else u
if other != v:
cover.discard(other)
if len(cover) < len(best) and is_cover(cover):
best = set(cover)
return best
approx2 = two_approx()
local = local_search(approx2, T * 0.9)
print(min(len(approx2), len(local)))
solve()Step-by-Step 解説
12-近似
最大マッチング M* の両端点。$|C| = 2|M*| \le 2|OPT|$。
最大マッチング M* の両端点。$|C| = 2|M*| \le 2|OPT|$。
2局所探索
頂点除去 → 未被覆辺の他端点追加 → 改善判定。
頂点除去 → 未被覆辺の他端点追加 → 改善判定。
3時間管理
time.time() で経過監視、時間制限の 90% で探索終了。
time.time() で経過監視、時間制限の 90% で探索終了。
4近似比
頂点被覆は UGC のもとで 1.5 未満不可能と予想。
頂点被覆は UGC のもとで 1.5 未満不可能と予想。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| is_cover 確認なし | 被覆崩れの可能性 | 最後に assert |
| time.time() 精度 | OS依存 | time.perf_counter() |
| 辺走査順依存 | 2-近似が変動 | ランダムシャッフルで安定化 |
次のステップ
- 最大独立集合（最小頂点被覆の補集合）