베시는 파머 존의 N(2 <= N <= 1,000) 헛간 중에서 편리하게 번호가 매겨진 저렴한 인터넷 네트워크를 구축하기 위해 고용되었습니다. FJ는 이미 몇 가지 설문조사를 실시한 결과, M(1 <= M <= 20,000) 개의 헛간 쌍 사이의 연결 경로가 가능하다는 것을 발견했습니다. 각 가능한 연결 경로에는 관련 비용이 C(1 <= C <= 10,000)입니다. 파머 존은 네트워크 연결에 최소한의 비용을 지출하고 싶어하지만, 베시에게 돈을 지불하고 싶지도 않습니다.
농부 존이 자신에게 돈을 주지 않을 것이라는 것을 깨달은 베시는 가능한 한 최악의 일을 하기로 결심합니다. 베시는 (i) 이러한 연결의 총 비용이 가능한 한 많이 들도록, (ii) 모든 헛간이 서로 연결되어 (설치된 연결 경로를 통해 다른 헛간에서 어느 헛간이든 도달할 수 있도록), (iii) 연결 사이에 주기가 없도록 (농부 존이 쉽게 감지할 수 있도록) 설치할 연결 세트를 결정해야 합니다. 조건 (ii) 및 (iii) 최종 연결 세트가 "나무"처럼 보이도록 합니다.
입력
라인 1: 두 개의 공간으로 구분된 정수: N과 M 라인 2..M+1: 각 라인에는 비용 C의 헛간 A와 B 사이의 연결 경로를 설명하는 세 개의 공간으로 구분된 정수 A, B, C가 포함되어 있습니다.
출력
라인 1: 모든 헛간을 연결하는 가장 비싼 나무의 가격을 포함하는 단일 정수입니다. 모든 헛간을 연결할 수 없는 경우 -1을 출력합니다.
rhtjdxo 1년 전 1
문제
베시는 파머 존의 N(2 <= N <= 1,000) 헛간 중에서 편리하게 번호가 매겨진 저렴한 인터넷 네트워크를 구축하기 위해 고용되었습니다. FJ는 이미 몇 가지 설문조사를 실시한 결과, M(1 <= M <= 20,000) 개의 헛간 쌍 사이의 연결 경로가 가능하다는 것을 발견했습니다. 각 가능한 연결 경로에는 관련 비용이 C(1 <= C <= 10,000)입니다. 파머 존은 네트워크 연결에 최소한의 비용을 지출하고 싶어하지만, 베시에게 돈을 지불하고 싶지도 않습니다.
농부 존이 자신에게 돈을 주지 않을 것이라는 것을 깨달은 베시는 가능한 한 최악의 일을 하기로 결심합니다. 베시는 (i) 이러한 연결의 총 비용이 가능한 한 많이 들도록, (ii) 모든 헛간이 서로 연결되어 (설치된 연결 경로를 통해 다른 헛간에서 어느 헛간이든 도달할 수 있도록), (iii) 연결 사이에 주기가 없도록 (농부 존이 쉽게 감지할 수 있도록) 설치할 연결 세트를 결정해야 합니다. 조건 (ii) 및 (iii) 최종 연결 세트가 "나무"처럼 보이도록 합니다.
입력
라인 1: 두 개의 공간으로 구분된 정수: N과 M
라인 2..M+1: 각 라인에는 비용 C의 헛간 A와 B 사이의 연결 경로를 설명하는 세 개의 공간으로 구분된 정수 A, B, C가 포함되어 있습니다.
출력
라인 1: 모든 헛간을 연결하는 가장 비싼 나무의 가격을 포함하는 단일 정수입니다. 모든 헛간을 연결할 수 없는 경우 -1을 출력합니다.