3805번 - 벌집들 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 103 | 32 | 21 | 33.333% |
문제
벌은 가장 근면성실한 곤충들 중의 하나입니다. 꽃에서 꿀과 꽃가루를 수집하기위해, 벌들은 숲 속의 나무들을 의지할 수 밖에 없습니다. 벌들은 작업을 단순하게 하기 위하여 n 개의 나무에 0 부터 n - 1 까지의 번호를 붙였습니다. 숲 전체를 돌아다니는 대신에, 경로들을 모아놓은 특정한 목록을 이용합니다. 하나의 경로는 두 개의 나무로 구성되고, 벌들은 어느 방향으로든 이동할 수 있습니다 (하나의 나무에서 다른 나무까지 직선으로). 그 목록에 없는 경로는 이용하지 않습니다.
기술이 꽤 발전하면서, 벌들은 일하는 전략 역시 변경했습니다. 숲 속에 있는 모든 나무들 위를 맴도는 대신에, 꽃들이 많은 특정 나무들을 목표로 삼고자 합니다. 그래서, 벌들은 목표한 몇몇 나무들에 새로운 벌집을 건설할 계획을 세웠습니다. 벌집이 모두 완성되면, 벌집이 있는 나무들에서만 식량을 모으려고 합니다. 그리고 벌집이 없는 나무에는 가지 않도록 하기 위해서 몇몇 경로들을 목록에서 지울 것 입니다.
자 이제, 벌들은 벌집을 건설하려고 합니다. 이 벌집들은 여러 경로 중 하나에 문제가 발생하더라도 (해당 경로 상에서 새나 동물들이 벌들을 방해할 수 있습니다.) 존재하는 다른 경로들을 이용해서 모든 벌집 간의 이동이 가능해야 합니다.
벌집 하나를 완성하는데는 많은 노력이 들기 때문에 벌들은 ,적어도 두 개 이상의 나무에, 가능한 적은 수의 벌집을 유지하고자 합니다. 이제 벌들이 이용하는 여러 경로와 나무를 이용해서, 새로운 벌집 군집를 제안해 봅시다.
입력
입력은 테스트 케이스들의 수를 나타내는 정수 T (T ≤ 50) 와 시작하고,
각각의 케이스는 하나의 빈 줄로 시작합니다. 다음 라인부터 두 개의 정수 n (2 ≤ n ≤ 500) 과 m (0 ≤ m ≤ 20000) 이 주어지고, n 은 나무들의 개수를 나타내고, m 은 경로들의 개수를 나타냅니다. 다음 m 라인은 두 개의 정수 u v (0 ≤ u, v < n, u ≠ v) 이고, 나무 u 에서 나무 v 로의 하나의 경로를 의미합니다. 나무 u 에서 나무 v 의 경로는 하나의 경로만 있다고 가정합니다. 말할 필요가 없긴 하지만, 입력으로 주어진 하나의 경로는 다시 주어지지 않을 것입니다.
출력
각각의 경우에 대해서, 문제 번호와 제안된 벌집 군집에서의 벌집의 개수를 출력하거나, 그러한 군집을 찾을 수 없다면 ‘impossible’을 출력합니다.
예제 입력 1
3 3 3 0 1 1 2 2 0 2 1 0 1 5 6 0 1 1 2 1 3 2 3 0 4 3 4
예제 출력 1
Case 1: 3 Case 2: impossible Case 3: 3
힌트
입력데이터가 큽니다. 빠른 I/O 처리를 이용하세요.
출처
ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2012 A번
- 문제를 번역한 사람: sgchoi5
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호