마법 도로 복구
골드 V의견: 0
마법사 왕국에는 \(N\)개의 도시가 있었지만, 폭풍으로 인해 모든 도로가 무너졌다. 왕은 왕국 재건을 위해 도로를 다시 건설하려 한다. 건설 가능한 도로의 후보 \(M\)개가 주어지는데, 각 도로는 두 도시와 건설 비용으로 이루어진다. 비용은 음수일 수 있다.
왕은 최소 비용으로 왕국의 모든 \(N\)개 도시를 연결하고 싶다. 즉, 임의의 두 도시 사이에 도로로 이어지는 경로가 존재하도록 도로의 부분 집합을 선택하되, 선택한 도로들의 건설 비용 합을 최소화해야 한다.
최소 비용의 합을 출력하여라. 단, 모든 도시를 연결하는 것이 불가능하면 \(-1\)을 출력한다.
- \(1 \le N \le 200\,000\)
- \(0 \le M \le 300\,000\)
- \(1 \le u, v \le N\), \(u \ne v\) (자기 루프 없음)
- \(-10^9 \le w \le 10^9\)
- 같은 두 도시를 잇는 도로는 최대 한 개이다.
첫째 줄에 도시의 수 \(N\)과 건설 가능한 도로의 수 \(M\)이 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 걸쳐, 각 줄에 도로 양 끝 도시 번호 \(u\), \(v\)와 건설 비용 \(w\)가 공백으로 구분되어 주어진다.
모든 도시를 연결할 수 있으면 최소 건설 비용의 합을, 그렇지 않으면 \(-1\)을 출력한다.
4 5
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
8
간선을 비용 오름차순으로 정렬하면 \(1, 2, 4, 5, 8\)이다. 비용 \(1\)(2번-3번), 비용 \(2\)(1번-3번), 비용 \(4\)(1번-2번)는 같은 컴포넌트라 건너뛰고, 비용 \(5\)(2번-4번)를 추가한다. 총 비용 \(1+2+5=8\)이다.
4 2
1 2 3
3 4 7
-1
도시 \(\{1,2\}\)와 \(\{3,4\}\) 사이를 잇는 도로가 없어 4개 도시를 모두 연결하는 것이 불가능하므로 \(-1\)을 출력한다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법 도로 복구
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 도로 복구