사용자 도구

사이트 도구


ps:problems:boj:8898

스포츠 전문 채널 GSK

ps
링크https://www.acmicpc.net/problem/8898
출처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)

코드

(다이아몬드 이상은 코드 생략)

토론

댓글을 입력하세요:
W​ Y S N Q
 
ps/problems/boj/8898.txt · 마지막으로 수정됨: 2022/03/28 08:36 저자 teferi