5979번 - 납땜하기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 91 | 20 | 16 | 29.091% |
문제
소들이 전선을 가지고 놀고 있다! 소들이 익힌 납땜 기술은 한 전선의 끝 부분을 다른 전선의 중간에 붙이는 것이다.(전선의 끝과 끝을 납땜하는 것은 허용되지 않는다.) 여러 전선이 한 부분에 납땜될 수도 있다.
소들은 자신들의 납땜 기술을 이용해 멋진 구조물을 만들고자 한다. 소들이 만들고자 하는 구조물은 서로 이어진 N개(1 <= N <= 50,000)의 정점과 N-1개의 단위 길이 간선으로 이루어진다. 각 간선은 두 쌍의 정수 A와 B로 구성되며,(1 <= A <= N; 1 <= B <= N; A != B) 이는 간선 양 끝의 정점 번호를 의미한다.
소들은 구조물을 만들기 위해 전선을 구입하려고 한다. 당연하게도 긴 전선은 비싸다. 구체적으로 말하자면 길이 L짜리 전선은 L*L 가격이 든다. 안타깝게도 전선을 자르거나 붙여서 사용할 수는 없다.
구조물의 설계도가 주어질 때, 소들은 전선들을 납땜해 구조물을 가장 저렴한 비용으로 만들고자 한다. 소들을 도와 소모되는 최저비용을 계산해보자.
점수의 50%에 해당하는 테스트 데이터는 N이 2,000보다 작다.
입력
- 첫 번째 줄: 정수 N
- 2~N번째 줄: 각 간선을 나타내는 정수 A와 B가 차례대로 입력된다.
출력
첫 번째 줄에 멋진 구조물을 만드는데 드는 최소비용을 출력한다. 정답이 32비트 정수형을 넘을 수도 있다.
예제 입력 1
6 1 2 1 3 1 4 1 5 1 6
예제 출력 1
7
힌트
구조물의 모든 정점이 1번 정점에 연결되어 있기 때문에, 길이 2짜리 전선 하나와 길이 1짜리 전선 세 개를 구매하면 된다. 총 비용은 2*2 + 1*1 * 3 = 7이 소모된다.
출처
Olympiad > USA Computing Olympiad > 2010-2011 Season > USACO US Open 2011 Contest > Gold 3번
- 문제를 번역한 사람: Qwaz
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호