2861번 - 원섭동 사람들 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 278 | 61 | 45 | 23.316% |
문제
원섭시에는 N명의 시민들이 살고 있다. 이 마을에 살고있는 모든 시민은 각각 다른 시민 1명에게 돈을 빌렸다. 이제 모든 빚을 갚아야하는 시간이다. 그런데, 큰 문제가 생겨서 모든 사람들이 돈을 갚을 수 없게 되었다. 그 이유는 각자 가지고 있는 돈을 모두 써버렸기 때문이다.
원섭시의 시장 고원섭은 이런 악순환을 해결하고자 마을에서 일부 사람들에게 돈을 주기로 했다. 이렇게 일부 사람들이 돈을 받게 되면, 그 돈으로 돈을 갚고, 또 받은 사람은 돈을 갚을 수 있게 된다. 예를 들어, A가 마을에서 돈을 받았다고 하자. 그럼 A는 B에게 돈을 갚을 수 있고, B는 C에게 돈을 갚을 수 있다. 만약, B가 빚을 갚을 수 있는 충분한 돈이 없다면, 충분한 돈이 생길 때 까지 기다리면 된다. 또, B가 돈을 더 가지고 있다면, B는 그 돈을 가지면 된다.
다른 예로, 이 마을에 두 사람이 살고 있고, 두 사람이 서로에게 100원을 빌린 경우를 생각해보자. 이 경우에 마을에서 두 사람 중 한 사람에게 100원을 주면, 서로 빚을 갚을 수 있게 된다.
원섭시의 모든 시민들의 채무 관계가 주어졌을 때, 마을의 악순환을 해결하기 위해 필요한 금액의 최솟값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 시민의 수 N (2 ≤ N ≤ 200,000)이 주어진다. 각 사람의 번호는 1번부터 N번이다.
다음 N개의 줄에는 공백으로 구분되어져 있는 두 정수 Ai와 Bi가 주어진다. Ai는 i번 사람이 돈을 빌린 사람의 번호이고, Bi는 갚아야 하는 금액이다. (1 ≤ Ai ≤ N, Ai ≠ i, 1 ≤ Bi ≤ 10,000)
출력
첫째 줄에 시민들의 빚을 해결하기 위해 필요한 최소 금액을 출력한다.
예제 입력 1
4 2 100 1 100 4 70 3 70
예제 출력 1
170
예제 입력 2
3 2 120 3 50 2 80
예제 출력 2
150
예제 입력 3
5 3 30 3 20 4 100 5 40 3 60
예제 출력 3
110
출처
Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #4 5번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호