ps:problems:boj:8898
목차
스포츠 전문 채널 GSK
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 8898 |
| 문제명 | 스포츠 전문 채널 GSK |
| 레벨 | 다이아몬드 3 |
| 분류 |
이분 매칭, 최대 반사슬 |
| 시간복잡도 | O(T*n^2.5) |
| 인풋사이즈 | T<=?, n<=1000 |
| 사용한 언어 | Python |
| 제출기록 | 39224KB / 3260ms |
| 최고기록 | 3260ms |
| 해결날짜 | 2022/03/28 |
풀이
- i번 경기의 취재를 마치고, j번 경기의 취재를 하는 것이 가능하다면, i≤j 라고 하자. 문제에서 주어진 조건상 이 관계는 추이적이고(i≤j이고 j≤k 이면 i≤k이다), 경기들은 부분 순서 집합을 이룬다.
- 결국 문제는 부분 순서 집합에서 최대 반사슬을 찾는 문제가 된다.
- 링크에서 설명한 대로, 이 문제는 이분 매칭을 이용해서 풀 수 있다. 최대 반사슬의 크기뿐만 아니라 집합도 구해야 하므로 최소 버텍스 커버를 구하고 그 여집합을 계산하는 과정이 필요하다. 어찌됐건 총 시간 복잡도는 O(sqrt(V)*E) = O(n^2.5)
코드
(다이아몬드 이상은 코드 생략)
- Dependency: teflib.tgraph.bipartite_matching
ps/problems/boj/8898.txt · 마지막으로 수정됨: 2022/03/28 08:36 저자 teferi
토론