문제
정올 웹사이트가 유명해짐에 따라, KOI준비를 위한 정올 캠프를 한 장소가 아닌 여러 장소에서 실시하기로 하였다.
실시간으로 여러 캠프 장소를 관리해야 하기 때문에, 정올 고유의 네트워크망을 구축하기로 하였다.
꽃미남 네트워크 전문가인 택쌤은 0번부터 n-1번까지, 총 n개의 캠프장에 네트워크망으로 연결하려고 한다.
총 m개의 광케이블 설치 허가가 났으며, 이는 s번 캠프장과 e번 캠프장을 값 c를 지불하고 광케이블로 연결할 수 있다는 형식이다.
세 캠프장 s, k, e에 있어서, s와 k가 연결되어 있고, k와 e가 연결되어 있으면, 이 세 캠프장은 모두 한 네트워크이다.
택쌤은 n개의 캠프장을 한 네트워크로 연결하려고 하는데, 최소 비용으로 연결하고 싶어한다.
택쌤을 도와 그 최소 비용을 구하는 프로그램을 작성하라.
입력
첫 줄에 n과 m이 공백을 사이에 두고 입력된다.
다음 m줄에 걸쳐서 s, e, c가 공백을 사이에 두고 입력된다.
이는 s와 e가 c의 값을 지불하고 광케이블로 연결할 수 있음을 의미한다. s와 e의 연결은 양방향 연결이다.
[부분문제의 제약 조건]
모든 입력에서 1<=n<=2,000, 1<=m<=4,000, 0<=s, e<=n-1, 1<=c<=50이다. 모든 입력되는 수는 정수이다.
부분문제 1: 전체 100점 중 10점에 해당하며, m줄에 걸쳐 입력되는 모든 c는 1이다.
부분문제 2: 전체 100점 중 30점에 해당하며,
어떤 두 캠프장 a와 b를 골라도 그 둘을 네트워크로 연결하는 방법은 존재하지 않거나 1가지뿐이다.
부분문제 3: 전체 100점 중 60점에 해당하며, 주어진 제약조건 외에 아무 제약조건이 없다.
출력
첫 줄에, 네트워크 구축에 필요한 최소 비용을 출력한다.
모든 캠프장을 네트워크로 연결할 방법이 존재하지 않는다면, -1을 출력한다.
예제 #1
5 6
0 4 5
0 1 7
0 3 2
4 2 3
3 4 1
2 1 4
10
예제 #2
4 3
1 0 5
1 3 2
3 0 4
-1
출처
Penn State CodePSU Advanced ? Problem A
로그인해야 코드를 작성할 수 있어요.