감시 카메라 최소 설치
플래티넘 I의견: 0
어떤 전시관의 통로 구조가 이분 그래프로 표현된다. 왼쪽에는 \(N\)개의 가로 복도, 오른쪽에는 \(M\)개의 세로 복도가 있고, 둘이 교차하는 곳마다 작품이 전시되어 있다.
교차점(작품)은 간선 \((a, b)\)로 주어진다. 각 복도(정점)에 카메라를 한 대 설치하면 그 복도에 속한 모든 교차점이 감시된다. 모든 교차점을 감시하기 위해 카메라를 설치해야 할 복도의 최소 개수와, 그러한 설치 방법 하나를 출력하여라.
\(1 \le N, M \le 50{,}000\)
\(0 \le E \le 200{,}000\)
\(1 \le a \le N\), \(1 \le b \le M\). 같은 간선이 중복으로 주어질 수 있다.
첫 줄에 왼쪽 복도 수 \(N\), 오른쪽 복도 수 \(M\), 교차점 수 \(E\)가 주어진다.
다음 \(E\)개의 줄에 각각 두 정수 \(a\), \(b\)가 주어지며, 이는 왼쪽 \(a\)번 복도와 오른쪽 \(b\)번 복도가 교차하는 작품을 의미한다.
첫 줄에 카메라를 설치할 복도의 최소 개수 \(K\)를 출력한다.
이어서 \(K\)개의 줄에 각 카메라의 위치를 출력한다. 왼쪽 \(i\)번 복도이면 L i, 오른쪽 \(j\)번 복도이면 R j 형식으로 출력한다(순서는 무관하며, 올바른 최소 덮개라면 어느 것이든 정답으로 인정된다).
3 3 4
1 1
1 2
2 2
3 3
3
L 1
L 2
L 3교차점은 (1,1),(1,2),(2,2),(3,3). 최대 매칭은 3 (예: 1-1, 2-2, 3-3). 쾨닉 정리로 최소 정점 덮개의 크기도 3이다. 예를 들어 오른쪽 복도 1,2,3에 설치하면 모든 교차점이 덮인다. 출력 형식상 한 가지 최소 덮개를 제시한다.
1 3 3
1 1
1 2
1 3
1
L 1왼쪽 복도 1이 오른쪽 복도 1,2,3과 모두 교차한다. 왼쪽 복도 1에 카메라 한 대만 설치하면 세 교차점이 모두 감시되므로 최소 개수는 1이다.
riseoj 작성
출처 Original
평가 및 의견
감시 카메라 최소 설치
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
감시 카메라 최소 설치