내용으로 건너뛰기
테페리넷
사용자 도구
등록
로그인
사이트 도구
검색
도구
원본 보기
Fold/unfold all
역링크
미디어 관리자
사이트맵
등록
로그인
>
미디어 관리자
사이트맵
현재 위치:
테페리넷
»
PS / Algorithm
»
문제
»
백준 온라인 저지 (BOJ)
»
스포츠 전문 채널 GSK
사이드바
테페리넷
주요 문서
시작
최근 추가된 문서
퍼즐
퍼즐게임
미궁
목록
더 라비린스
카톡방탈출
PS/Algorithm
문제 목록
백준 온라인 저지
( 437 )
프로그래머스
( 104 )
알고리즘 정리
관리자 전용
관리자 페이지
ps:problems:boj:8898
목차
스포츠 전문 채널 GSK
풀이
코드
토론
스포츠 전문 채널 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)
코드
(다이아몬드 이상은 코드 생략)
Dependency:
teflib.tgraph.bipartite_matching
BOJ
,
다이아몬드 3
토론
실명:
이메일:
웹사이트:
댓글을 입력하세요:
인간임을 증명하기 위해 상자에 있는 모든 글자를 채워주세요.
W Y S N Q
이 필드는 비어 있도록 유지하세요:
댓글 구독
ps/problems/boj/8898.txt
· 마지막으로 수정됨: 2022/03/28 08:36 저자
teferi
문서 도구
원본 보기
역링크
Fold/unfold all
맨 위로
토론