1772번 - 정원 정리 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 280 | 116 | 95 | 60.897% |
문제
정원을 정리하던 배상욱은 흉측할 정도로 난잡하게 자란 정원수 한 그루를 발견했다. 가지치기를 할 시기가 된 것이다.
정원수는 n개의 정점과 n-1개의 간선으로 구성된, 연결 그래프로 표현된다. 그래프 내의 정점은 정원수의 잎사귀라고 할 수 있으며, 각 간선은 정원수의 가지들이라고 생각하자.
상욱은 가지치기를 통해 정원수 내의 잎사귀 개수가 m이 되도록 만드는 것이다. 즉, 정원수를 나타내는 그래프 내에 m개의 정점만 남겨야 한다. 가지치기란, 정원수 그래프 내의 간선을 끊는 일이다. 특정한 간선을 끊어, 그래프가 두 부분으로 분리되면, 한 부분을 취하고 다른 부분은 버린다.
상욱은 그리 부지런한 사람이 아닌 관계로, 최소한의 가지치기를 이용해서 정원수를 정리하기를 바란다. 정원수의 모양이 주어지면, 어떻게 가지치기를 해야 최소한의 가위질로 작업을 마무리할 수 있을지 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 n과 m이 주어진다. (1<=n<=150, 1<=m<=n) 이후 한 줄에 한 개씩, 정원수의 가지를 나타내는 정보가 주어진다. 이는 정원수 내의 잎사귀 번호 두 개로 이루어져 있으며, 두 잎사귀 사이를 연결하는 가지가 있다는 의미이다. 잎사귀 번호는 1이상 n이하의 정수이다.
출력
첫째 줄에, 최소한의 가지치기 횟수를 출력한다. 불가능한 경우에는 -1을 출력한다.
예제 입력 1
11 6 1 2 1 3 1 4 1 5 2 6 2 7 2 8 4 9 4 10 4 11
예제 출력 1
2
힌트
예시의 경우, 1-4, 1-5 두 개의 간선을 제거하면 원하는 크기의 정원수를 얻을 수 있다.
출처
Olympiad > USA Computing Olympiad > 2001-2002 Season > USACO February 2002 Contest > Green or Orange ?번
- 문제를 번역한 사람: author5
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호