30807번 - TSM 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 8 초 | 1024 MB | 373 | 103 | 89 | 30.690% |
문제
가중치 있는 그래프가 주어졌을 때, 최소 스패닝 트리(MST)의 비용을 구하는 문제는 잘 알려져 있습니다. 최소 스패닝 트리의 비용이 주어졌을 때, 그래프의 간선에 가중치를 부여하는 문제를 해결하세요.
자세한 설명은 아래와 같습니다.
- 최소 스패닝 트리란, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 비용이 최소인 트리를 뜻합니다. 스패닝 트리의 비용은 트리에 포함된 간선의 가중치 합으로 정의합니다.
- 주어지는 그래프는 $N$개의 정점과 $M$개의 간선을 가진 무방향 연결 그래프입니다. 각 정점과 각 간선에는 $1$번부터 순서대로 번호가 붙어 있습니다. $i$번 간선은 $u_i$번 정점과 $v_i$번 정점을 이으며, $i$번 간선에는 $l_i$ 이상 $r_i$ 이하의 정수 가중치를 부여할 수 있습니다.
- 각 간선에 적절한 가중치를 부여해서 최소 스패닝 트리의 비용이 $K$가 되도록 만드세요.
입력
첫 번째 줄에 그래프의 정점의 수 $N$과 간선의 수 $M$, 최소 스패닝 트리의 비용 $K$가 공백으로 구분되어 주어집니다. $(2 \le N \le 100\, 000;\ N-1 \le M \le 200\, 000;\ 0 \le K \le 10^{10})$
다음 $M$개의 줄의 $i$번째 줄에 정수 $u_i, v_i, l_i, r_i$가 공백으로 구분되어 주어집니다. $i$번 간선이 $u_i$번 정점과 $v_i$번 정점을 이으며, $i$번 간선에 $l_i$ 이상 $r_i$ 이하의 정수 가중치를 부여할 수 있음을 의미합니다. $(1 \le u_i, v_i \le N;\ u_i \ne v_i;\ 0 \le l_i \le r_i \le 100\, 000)$
주어지는 그래프는 연결 그래프이며, 서로 다른 간선은 같은 정점 쌍을 잇지 않습니다.
출력
스패닝 트리의 비용이 $K$가 되도록 가중치를 부여할 수 있다면 첫 줄에 YES, 불가능하다면 NO를 출력합니다.YES를 출력한 경우 추가로 $M$개의 줄을 출력합니다. 그중 $i$번째 줄에는 $i$번째 간선에 부여할 가중치를 출력합니다.
예제 입력 1
4 5 10 1 2 0 5 1 3 7 9 1 4 1 6 2 4 3 4 3 4 2 2
예제 출력 1
YES 5 7 4 4 2
예제 입력 2
4 5 12 1 2 0 5 1 3 7 9 1 4 1 6 2 4 3 4 3 4 2 2
예제 출력 2
NO
출처
Contest > solved.ac > solved.ac Grand Arena #3 > Division 2 F번
Contest > solved.ac > solved.ac Grand Arena #3 > Division 1 B번
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호