1815번 - 방송국 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 12 | 7 | 5 | 83.333% |
문제
월드 방송국에서 유선으로 방송을 하고자 한다. 방송망의 형태는 방송국이 루트인 트리의 형태가 될 것이다. 트리의 터미널 노드들은 사용자를 의미하며 트리에서 터미널을 제외한 노드는 송신기 역할을 하게 된다. (루트는 방송국이면서 송신기이며, 루트와 터미널이 아닌 노드들은 중간 송신기라고 불려진다)
한 노드에서 다른 노드로 방송 라인을 설치할 때 드는 비용이 주어진다. 총 방송 비용이란 설치한 방송 라인의 비용을 모두 더한 값이다.
같은 방송망에 있지만 각각의 사용자가 내는 돈은 다를 수 있으며 각각 사용자가 방송을 보게 될 때 지불할 돈이 미리 주어진다
방송국에서는 방송 라인을 하나 설치할 때 지출을 하게 된다. 또한 방송망이 방송국에서 사용자까지 도달되면 방송국은 그 사용자에게서 시청료를 받게 된다.
방송라인을 적절히 설치해서 방송국이 손해를 보지 않으면서 방송을 해줄 수 있는 최대 사용자는 몇 명인가? (손해를 보지 않는다는 말은 총 시청료 - 총 방송 비용 ≥ 0 임을 의미한다)
입력
첫 줄에 N M이 입력된다. (2 ≤ N ≤ 3,000, 1 ≤ M ≤ N-1) N은 트리의 노드 개수이고 M은 트리의 터미널 노드 개수이다. 노드의 번호는 트리의 루트가 1이며, 루트가 아닌 다른 송신기들은 2부터 N-M까지, 사용자들(터미널노드들)의 번호는 N-M+1부터 N까지 이다.
두 번째 줄부터 N-M개의 줄에 다음과 같은 형식으로 송신기 정보가 주어진다.
K A1 C1 A2 C2 ... Ak Ck
K는 그 송신기가 송신하는 노드의 개수이며 A는 그 노드의 이름 C는 그 비용을 의미한다. 그 이후의 M개의 라인에는 M명의 사용자의 시청료가 각각 입력된다.
출력
최대 사용자 수를 출력한다.
예제 입력 1
5 3 2 2 2 5 3 2 3 2 4 3 3 4 2
예제 출력 1
2
예제 입력 2
5 3 2 2 2 5 3 2 3 2 4 3 4 4 2
예제 출력 2
3
예제 입력 3
9 6 3 2 2 3 2 9 3 2 4 2 5 2 3 6 2 7 2 8 2 4 3 3 3 1 1
예제 출력 3
5
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2002 > Final Exam #2 1번
- 문제를 번역한 사람: author6
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호