케이블카 관광 가치
골드 IV의견: 0
산악 지대의 \(n\) 개 마을을 케이블카로 연결하려고 한다. 두 마을을 잇는 케이블카 후보 노선이 \(m\) 개 있으며, 각 노선에는 관광 가치가 매겨져 있다.
회사는 모든 마을이 서로 (직접 또는 간접적으로) 연결되도록 노선 몇 개를 선택하려고 하는데, 선택한 노선들의 관광 가치 합이 최대가 되도록 하면서도 불필요한 노선은 짓지 않으려 한다. 즉, 마을이 \(n\) 개일 때 정확히 \(n-1\) 개의 노선만 선택하여 전체를 연결한다.
이때 선택한 노선들의 관광 가치 합의 최댓값을 구하여라. 모든 마을을 연결하는 것이 불가능하면 \(-1\) 을 출력한다.
\(1 \le n \le 100{,}000\), \(1 \le m \le 150{,}000\), \(1 \le w \le 10^6\)
첫째 줄에 마을의 수 \(n\) 과 노선 후보의 수 \(m\) 이 주어진다. (\(1 \le n \le 100{,}000\), \(1 \le m \le 150{,}000\))
다음 \(m\) 개의 줄에 세 정수 \(u\ v\ w\) 가 주어지며, 마을 \(u\) 와 \(v\) 를 잇는 관광 가치 \(w\) 의 노선을 의미한다. (\(1 \le u, v \le n\), \(u \ne v\), \(1 \le w \le 10^6\))
관광 가치 합의 최댓값을 출력한다. 전체 연결이 불가능하면 \(-1\) 을 출력한다.
4 5
1 2 3
2 3 4
3 4 5
1 4 1
1 3 212가치가 큰 노선부터 선택하면 \(3-4(5),\ 2-3(4),\ 1-2(3)\) 을 골라 모두 연결되며 합은 12로 최대.
3 1
1 2 5-1마을 3을 연결할 노선이 없어 전체 연결이 불가능하므로 \(-1\).
riseoj 작성
출처 Original
평가 및 의견
케이블카 관광 가치
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
케이블카 관광 가치