스포츠 전문 채널 GSK

• i번 경기의 취재를 마치고, j번 경기의 취재를 하는 것이 가능하다면, i≤j 라고 하자. 문제에서 주어진 조건상 이 관계는 추이적이고(i≤j이고 j≤k 이면 i≤k이다), 경기들은 부분 순서 집합을 이룬다.
• 결국 문제는 부분 순서 집합에서 최대 반사슬을 찾는 문제가 된다.
• 링크에서 설명한 대로, 이 문제는 이분 매칭을 이용해서 풀 수 있다. 최대 반사슬의 크기뿐만 아니라 집합도 구해야 하므로 최소 버텍스 커버를 구하고 그 여집합을 계산하는 과정이 필요하다. 어찌됐건 총 시간 복잡도는 O(sqrt(V)*E) = O(n^2.5)

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

• Dependency: teflib.tgraph.bipartite_matching