안전한 비상연락망 > 문제은행

본문 바로가기


문제은행

2800 : 안전한 비상연락망

제한시간: 1Sec    메모리제한: 128mb
해결횟수: 14회    시도횟수: 329회   



산골에 N 개의 마을이 있으며 각각 두 마을을 잇는 M 개의 도로가 있다. 이 도로들은 전체 마을들을 모두 연결하고 있다. 즉, 어떤 마을에서든 다른 마을로 (하나 이상의 도로를 거쳐서) 갈 수 있다. 또한 어떤 인접한 두 마을은 두 개 이상의 도로로 바로 연결되기도 한다. 여러 가지 급한 상황이 생길 수 있기 때문에 전체 마을들을 연결하는 비상연락망을 구성하여 급한 상황을 알리기로 하였다. 비상연락망에 들어가는 도로의 경우에는 특별히 잘 관리해야 하므로 각 도로마다 관리 비용이 발생한다. 물론 비상연락망은 전체 관리 비용이 최소가 되도록 만든다.

 

이 지역에는 가끔 산사태가 발생하는데, 산사태가 발생하여 특정한 도로가 통행 불가능이 될 수 있다. 다행히도 통행 불가능이 되는 경우 오직 하나의 도로만이 그렇게 된다고 한다.

 

그러한 상황에 대비하기 위해서 각 도로마다, 그 도로가 통행 불가능이 되었다고 가정하고 비상연락망을 구성할 경우 전체 최소 비용이 얼마가 되는지 알고 싶다.

 

dbf6c632c6fe635a92e18a501eea7c63_1454392 


그림-1은 어떤 산골마을의 예이다. 원이 마을이며, 선분이 도로이고, 도로 옆의 수는 그 도로에 해당하는 비용이다.

 

dbf6c632c6fe635a92e18a501eea7c63_1454392


그림-2는 모든 도로가 통행이 가능할 때의 비상연락망 구성이며, 굵은 선으로 표현된 도로들이 비상연락망에 포함된 것이다. 이때 전체 비용은 13이다.

 

dbf6c632c6fe635a92e18a501eea7c63_1454392


그림-3은 2번과 5번 마을을 잇는 도로가 통행 불가능인 경우의 비상연락망이며, 비용은 14이다.

 

dbf6c632c6fe635a92e18a501eea7c63_1454392


그림-4는 1번과 2번 마을을 잇는 도로가 통행 불가능인 경우이며, 비용은 15이다.

 

마을의 수와 연결하는 도로들, 그리고 각 도로에 해당하는 비용을 입력으로 받아서 각각의 도로에 대해서 그 도로가 통행 불가능인 경우의 비상연락망을 구성하는 최소 비용을 출력하는 프로그램을 작성하라.


입력의 첫 줄에는 마을의 수 N ( 2 ≤ N ≤ 100,000 )과 도로의 수 M ( 2 ≤ M ≤ 300,000 )이 자연수로 주어진다.
각 마을은 1번부터 번호가 붙은 것으로 생각한다. 이후 M 개의 줄에는 각각 3개의 자연수가 주어지는데, 첫 두 자연수는 해당 도로가 잇는 두 마을의 번호이며, 세 번째 자연수는 그 도로가 비상연락망에 포함될 경우의 관리 비용이다. 비용은 0 이상 109 이하이다.

하나의 마을 쌍에 대해 여러 개의 도로가 존재할 수도 있으며, 서로 다른 도로가 같은 비용 값을 가질 수도 있음에 주의하라.

<제약조건>
• 부분문제 1: 전체 점수 100점 중 7점에 해당하며 N ≤ 5, M ≤ 10 이다.
• 부분문제 2: 전체 점수 100점 중 16점에 해당하며 N ≤ 100, M ≤ 1,000 이다.
• 부분문제 3: 전체 점수 100점 중 11점에 해당하며 N ≤ 1,000, M ≤ 10,000 이다.
• 부분문제 4: 전체 점수 100점 중 27점에 해당하며 N ≤ 5,000, M ≤ 20,000 이다.
• 부분문제 5: 전체 점수 100점 중 39점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.


출력에는 M 개의 줄이 있어야하며, 각 줄에는 하나의 자연수가 있어야 한다. i 번째 줄에는 입력에 i 번째로 주어진 도로가 통행 불가능인 경우 비상연락망의 최소 비용을 자연수로 출력한다.

단, 비상연락망이 존재하지 않는다면 -1을 출력해야 한다. 비용의 값이 커질 수 있으므로 64비트 정수 변수(long long type)를 사용해야 할 수도 있음에 주의하라.

[Copy]
5 9
1 2 1
3 1 4
4 3 6
2 4 7
2 5 2
5 3 5
1 5 3
5 4 7
2 4 8
[Copy]
15
14
14
13
14
13
13
13
13


[Copy]
4 4
1 2 1
2 3 2
2 4 3
4 3 2
[Copy]
-1
6
5
6




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.