사이클코스(Trainings) > 문제은행

본문 바로가기


문제은행

1107 : 사이클코스(Trainings)

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 4 회    시도횟수: 7 회   



미르코와 슬라브코는 크로아티아에서 해마다 열리는 2인승 사이클 장거리 경주의 참가를 앞두고 열심히 기량을 쌓고 있다. 그들은 연습 코스를 설정해 놓고 그 코스대로 꾸준히 주행 연습을 하고 싶어한다.

 

주변에는 N개의 도시와 M개의 길이 있다. 길은 두 도시를 연결하며 어느 방향으로나 주행이 가능하다. M개의 길 중 정확하게 N-1개는 포장된 도로이며, 나머지는 비포장 오솔길이다. 단, 모든 도시는 포장도로만으로도 상호 왕래가 가능하게 연결돼 있다. 다시 말해 N개의 도시와 N-1개의 포장도로는 트리 구조를 형성한다는 뜻이다.

 

아울러, 한 도시를 관통하는 길(포장, 비포장 막론)의 최대 개수는 10개이다.

 

연습 코스는 한 도시에서 시작해서 임의의 길을 따라 운행한 뒤, 다시 그 도시로 돌아오는 형태이다. 미르코와 슬라브코는 늘 새로운 길을 가는 것을 좋아하기 때문에, 전에 지나쳤던 도시를 또 들르거나 전에 주행했던 도로를 다시 주행하는 일이 없도록 코스를 만들고 싶어 한다. 코스는 아무 도시에서나 시작해도 되며, 모든 도시를 다 거쳐야 할 필요는 없다.

 

2인승 자전거는 뒤에 타는 게 체력 소모가 더 적다. 앞 사람이 역풍을 가려 주기 때문이다. 그래서 둘은 새로운 도시에 도착할 때마다 자리를 교대한다. 이런 상황에서 두 사람이 서로 동일한 양만치 훈련을 하기 위해서는 연습 코스는 짝수 개의 길을 경유하도록 정해야 한다.

 

그런데 미르코와 슬라브코를 시샘하는 경쟁자들은, 길의 일부를 폐쇄함으로써 그 두 사람이 위에서 언급한 모든 조건을 만족하는 연습 코스를 전혀 찾을 수 없게 만들기로 작정했다. 비포장 길은 폐쇄하는데 제각기 비용이 들며, 그 비용은 양의 정수로 표현된다. 다만 포장도로는 폐쇄가 불가능하다.

 

도시와 도로망에 대한 정보를 입력 받아, 위에서 언급한 모든 조건을 만족하는 사이클 연습 코스가 존재하지 않게 만드는데 필요한 최소한의 도로 폐쇄 비용을 계산하는 프로그램을 작성하시오.


첫째 줄에는 도시의 개수 N과 길의 개수 M이 있다. (2≤N≤1000, N-1≤M≤5000) 그리고 다음 M개의 줄에는 길의 정보를 나타내는 정수 A, B, C가 있다. (1≤A≤N, 1≤B≤N, 0≤C≤10,000) 도시 A와 도시 B가 길로 연결되어 있으며, 이 길의 폐쇄 비용이 C임을 의미한다. 단, C가 0이면 이 길은 폐쇄할 수 없는 포장 도로라는 뜻이다.

그래프 상으로 한 도시 정점에 붙을 수 있는 도로 선분의 최대 개수는 앞서 말했듯이 10이다. 임의의 두 도시를 연결하는 도로는 최대 하나밖에 존재하지 않는다. (당연한 말임. 즉, 한 직통 도로가 막혔다고 해서 다른 직통 도로를 이용하면 되는 상황까지 고려하지는 않아도 된다는 뜻.)



문제 조건을 충족하기 위해 막아야 하는 길들의 폐쇄 비용의 합을 정수로 출력하면 된다.


[Copy]
5 8
2 1 0
3 2 0
4 3 0
5 4 0
1 3 2
3 5 2
2 4 5
2 5 1
[Copy]
5




IOI 2007 day2_3 training

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.