16202번 - MST 게임 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 1488 | 981 | 732 | 67.094% |
문제
N개의 정점과 M개의 양방향간선으로 이루어진 단순 그래프 G가 있다. 단순 그래프란, self-loop 간선(한 정점에서 자기 자신을 이어주는 간선)이 없고, 임의의 두 정점 사이 최대 한 개의 간선이 있는 그래프를 말한다. 단순 그래프의 스패닝 트리(Spanning Tree)는 다음 조건을 만족하는 간선의 집합이다.
- 스패닝 트리를 구성하는 간선의 개수는 N-1개이다.
- 그래프의 임의의 두 정점을 골랐을 때, 스패닝 트리에 속하는 간선만 이용해서 두 정점을 연결하는 경로를 구성할 수 있어야 한다.
스패닝 트리 중에서 간선의 가중치의 합이 최소인 것을 최소 스패닝 트리(Minimum Spanning Tree, MST)라고 부른다.
이제 그래프에서 MST 게임을 하려고 한다.
- MST 게임은 그래프에서 간선을 하나씩 제거하면서 MST의 비용을 구하는 게임이다. MST의 비용이란 MST를 이루고 있는 가중치의 합을 의미한다. 각 턴의 점수는 해당 턴에서 찾은 MST의 비용이 된다.
- 이 과정은 K턴에 걸쳐서 진행되며, 첫 턴에는 입력으로 주어진 그래프의 MST 비용을 구해야 한다.
- 각 턴이 종료된 후에는 그 턴에서 구한 MST에서 가장 가중치가 작은 간선 하나를 제거한다.
- 한 번 제거된 간선은 이후의 턴에서 사용할 수 없다.
- 어떤 턴에서 MST를 만들 수 없다면, 그 턴의 점수는 0이다. 당연히 이후 모든 턴의 점수도 0점이다. 첫 턴에 MST를 만들 수 없는 경우도 있다.
양방향 간선으로 이루어진 단순 그래프와 K가 주어졌을 때, 각 턴의 점수가 몇 점인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 그래프 정점의 개수 N, 그래프 간선의 개수 M, 턴의 수 K가 주어진다. (2 ≤ N ≤ 1,000, 1 ≤ M ≤ min(10,000, N×(N-1)/2), 1 < K ≤ 100)
그 후 M개의 줄에 간선의 정보가 주어진다. 간선의 정보는 간선을 연결하는 두 정점의 번호 x, y로 이루어져 있다. 같은 간선이 여러 번 주어지는 경우는 없다. 간선의 가중치는 주어지는 순서대로 1, 2, ..., M이다.
정점의 번호는 1부터 N까지로 이루어져 있다.
출력
한 줄에 공백으로 구분하여 K개의 정수를 출력해야 한다. K개의 정수는 각 턴에 얻는 점수를 나타낸다.
예제 입력 1
6 6 2 1 2 2 3 1 3 4 5 5 6 4 6
예제 출력 1
0 0
첫 턴에 MST를 찾을 수 없어서 모든 턴의 점수가 0이 된다.
예제 입력 2
6 7 3 2 4 1 2 4 6 1 3 2 3 4 5 5 6
예제 출력 2
16 0 0
예제 입력 3
4 5 4 3 4 1 3 1 4 1 2 2 4
예제 출력 3
7 9 0 0
예제 입력 4
5 7 4 1 2 2 3 3 4 4 5 1 5 1 4 1 3
예제 출력 4
10 14 0 0
예제 입력 5
6 9 6 1 2 2 3 3 4 4 5 5 6 1 6 1 4 2 5 3 6
예제 출력 5
15 20 26 32 35 0
힌트
첫 턴에 찾을 수 있는 MST는 총 5개의 간선 {(1, 3), (1, 2), (2, 4), (4, 6), (4, 5)}로 이루어져 있고, 비용은 16이다.
두 번째 턴에는 첫 턴에서 구한 MST에서 간선의 비용이 최소인 (2, 4)를 제거한 후 남아있는 간선을 이용해 MST를 찾아야 한다. 하지만, (2, 4)를 없앤 후 MST가 존재하지 않기 때문에, 두 번째 턴과 그 이후 모든 턴의 점수는 0이 된다.
출처
- 문제를 만든 사람: haden
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호