유능한 비서 (Efficient Secretary)

문제

인덱스국 도로교통 : Day 2

인덱스국의 왕 (검열됨)은 왕국의 도로를 재정비하여 유지비를 절약하기 위해 왕국에 있는 도로를 조사 하도록 명하였고, 인덱스 트리밖에 못 짜는 그의 신하들은 N 개의 도시 사이를 연결하는 M개의 도로밖에 찾지 못했습니다. i번째 도로는 도시 S[i]와 E[i]를 연결합니다. (0 ≤ i ≤ M − 1) 그러나 무능한 신하 들이 기억하고 있는 정보는 도로들을 이용해 모든 도시 사이를 이동할 수 있다는 정보 뿐이라고 합니다.

(검열됨)은 이 도로들 중 N − 1개의 도로만을 골라서 모든 도시들이 연결되도록 만드려고 합니다.

그러나 (검열됨)의 유일하게 유능한 신하인 비서는 자신에게 돈이 되는 일이 아니면 아무것도 하지 않습니다. (검열됨)은 비서에게 어떤 도로를 골라야 좋을지 물어봤지만, 비서는 (검열됨)의 질문을 차갑게 무시했습니다. 그러나 비서에게 각 도로의 보수비용을 알려주면, 돈 얘기만 듣고 흥분한 비서는 가장 저렴하게 모든 도시를 연결하는데 필요한 비용을 알려준다고 합니다.

그러나 비서에게 너무 많은 질문을 하면, 돈이 되지 않는다는 것을 알아차리고 사표를 쓸 지도 모릅니다.

또, 질문을 했을 때 어떤 도로의 보수비용이 비상식적인 수준이라면, 비서는 (검열됨)의 의도를 눈치채고 다시 질문을 무시할 지도 모릅니다. (검열됨)은 700번 이하의 질문으로 모든 도시를 연결하기 위해 골라야 할 도로들의 집합을 구하려고 합니다.

구현 세부 사항

다음 함수를 구현하세요.

int[] getKingdomRoads(int N, int M)

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.
• 이 함수는 모든 도시들을 연결할 수 있는 N − 1개의 도로 번호를 반환해야 합니다.

함수 getKingdomRoads는 다음 함수를 호출할 수 있습니다.

int getMinimumCost(int C[])

• 이 함수는 i번 도로의 보수비용을 나타내는 C[i]를 인자로 받습니다.
• 이 함수는 가장 저렴하게 모든 도시를 연결하는데 필요한 비용을 반환합니다.

제한 조건

• 1 ≤ N ≤ 80
• N ≤ M ≤ 8,000
• 1 ≤ S[i], E[i] ≤ N (0 ≤ i ≤ M − 1)
• 모든 도시들 간에 도로들을 이용하여 이동할 수 있습니다.
• 1 ≤ C[i] ≤ 1,024
• getMinimumCost 함수는 최대 700번 호출할 수 있습니다.

서브태스크

P 는 다음과 같이 계산됩니다. P = $\lceil \log_2(\max(C[i])) \rceil$

서브태스크	점수	N, M	P
1	2	N ≤ M ≤ 6	P ≤ 5
2	2	N ≤ 80, M ≤ 600	P ≤ 1
3	6	N ≤ 80, M ≤ 6,000	P ≤ 10
4	6	N ≤ 50, M ≤ 8,000	P ≤ 1
5	4	N ≤ 80, M ≤ 8,000	P ≤ 1

예제 입출력

N = 3, M = 6, S = [1, 2, 3, 1, 2, 3], E = [1, 3, 2, 2, 1, 2]

그레이더는 다음 함수를 호출합니다.

getKingdomRoads(3, 6)

getKingdomRoads는 getMinimumCost를 호출하여 답을 찾습니다.

getMinimumCost([1, 2, 3, 5, 6, 7]) = 7

getKingdomRoads는 답인 [1, 3]을 반환합니다.

샘플 그레이더

Sample grader는 다음의 형식으로 입력을 받습니다.

• line 1 : N M
• line 2 + i (0 ≤ i ≤ M − 1) : S[i] E[i]