AT2645 [ARC076D] 최소 의자 추가 문제
해결 방법 1
보조정리: 이분 그래프의 두 부분집합을 각각 X, Y(|X| ≤ |Y|)라고 할 때, 완벽한 매칭이 존재할 필요충분조건은 ∀S ⊆ X, f(S) ≥ |S| (여기서 f(S)는 S와 연결된 점들의 집합)이다. (즉, 홀의 정리)
문제에서 요구하는 것은 기본적으로 완벽한 매칭을 구성하기 위해 최소 몇 개의 의자를 추가해야 하는지를 묻고 있습니다.
따라서 모든 사람이 의자를 선택할 ...
7월 31일 18:34에 게시됨