9279번 - 얼어붙은 스프링쿨러 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 128 MB | 174 | 61 | 52 | 42.975% |
문제
이번 겨울은 100년 만에 가장 추운 겨울이라고 한다. 해빈시는 겨울을 대비해서 공원이 망가지지 않다로고 조치를 취하려고 한다. 가장 먼저 스프링쿨러에 남아있는 물을 제거해야 한다.
중앙 노드에서 분배된 물은 모두 파이프를 통해 이웃한 노드로 흘러간다. 모든 노드는 스프링쿨러이거나 물을 분배하는 내부 노드이다. 자세한 설명은 아래에 나와있다.
- 우물과 직접 연결된 중앙 노드를 제외한 모든 노드는 모두 물을 공급받는 파이프를 단 하나 가지고 있다.
- 모든 내부 노드는 다른 노드로 물을 분배하는 파이프를 하나 이상 가지고 있다. 즉, 스프링클러는 물을 내보내는 파이프를 가지고 있지 않다.
- 모든 파이프에는 밸브가 달려있어서 물이 흐르지 않도록 할 수 있다. 이때, 각 밸브를 잠그는 데 필요한 힘은 다르다.
해빈시의 공무원 신해빈은 스프링쿨러 시스템을 완벽하게 이해하고 있고, 각 밸브를 잠그는데 필요한 힘의 양을 알고 있다.
게으른 해빈이는 최소한의 힘을 사용해 몇 개의 밸브를 잠궈 모든 스프링쿨러에 물이 공급되지 않도록 하려고 한다.
과연 힘이 얼마만큼 필요할까?
입력
입력은 여러 개의 테스트 케이스로 이루어져있다.
각 테스트 케이스는 노드의 개수를 나타내는 N (2 ≤ N ≤ 1 000)과 중앙 노드의 번호를 나타내는 C (1 ≤ C ≤ N)로 시작된다.
이후 N-1개의 줄에는 각 파이프의 정보를 나타내는 세 정수 u, v (1 ≤ u, v ≤ n) 와 w (1 ≤ w ≤ 1 000)가 주어지는데, 이는 u와 v를 연결하는 파이프가 존재하고, 이 파이프의 밸브를 잠그는 데 w만큼의 힘이 필요하단 뜻이다.
출력
각 테스트 케이스마다 모든 스프링쿨러로 더 이상 물이 흘러들어가지 않도록 밸브를 잠그는 데 필요한 최소한의 힘을 출력한다.
예제 입력 1
3 1 2 1 5 1 3 4 7 7 7 6 10 7 5 10 6 4 1 6 3 1 5 2 1 5 1 2
예제 출력 1
9 5
출처
ICPC > Regionals > Europe > Central European Regional Contest > CTU Open Contest > CTU Open Contest, 2013 R번
- 문제를 번역한 사람: WeissBlume
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호