화물 트럭 > 문제은행



문제은행

3209 : 화물 트럭

제한시간: 2000 ms    메모리제한: 256 MB
해결횟수: 0 회    시도횟수: 5 회   



정올국엔 0번부터 (n-1)번까지 지정되어 있는 총 n개의 도시가 있다. 이는 m개의 양방향 도로로 연결되어 있다. 어떤 두 도시 i, j를 뽑더라도 i번 도시부터 j번 도시까지 직접 또는 다른 도시를 경유해서 가는 경로는 무조건 존재한다.

 

정올국의 대규모 도로 포장 정책으로, 모든 도로는 새것이 되었다. 그래서 초기에, 모든 도로의 부식도는 0이다. 화물 트럭이 한번 지나갈 때마다, 그 도로의 부식도는 1씩 증가한다.

 

정올국은 아직 t번의 도로 수리를 더 해줄 수 있는 예산이 있다. 한 번 수리할 때 마다, 도로의 부식도는 1씩 감소한다. 한 도로를 여러 번 수리하는 것도 가능하다.

 

화물 트럭의 내구도는 거쳐왔던 도로 중 가장 높은 부식도를 가진 도로의 부식도 만큼 감소한다. 내구도 감소가 클수록, 트럭의 질이 떨어진다.

 

철기는 정올 우체국택배의 매니저이다. 철기의 목표는 k개의 트럭을, 0번 도시부터 n-1번 도시까지 보내는 것이다. 철기는 k개의 트럭 중 내구도가 가장 많이 감소한 트럭의 내구도 감소가 최소화될 수 있도록 하고 싶다.

 

철기를 도와 k개의 트럭 중 최대로 내구도가 감소한 트럭이 최소의 피해를 입는 경우, 그 최대 내구도 감소도를 출력하는 프로그램을 작성하라.​ 

 




첫 줄에 네 정수인 n, m, k, t가 차례로 주어진다. n, m, k, t는 모두 1 이상 2,000 이하이다.
다음 m 줄에는 두 정수 u, v가 들어오며, 이는 u번 도시와 v번 도시 사이에 양방향 도로가 있다는 뜻이다.
u와 v는 모두 0이상 n 미만이다.



가장 손상이 심한 트럭의 내구도 감소를 최소화시키는 경우, 그 트럭의 내구도 감소도를 출력한다.


7 8 2 0
0 1
0 2
1 3
2 3
3 4
3 5
4 6
5 6
 0


5 5 2 1
0 1
1 2
1 3
2 4
3 4
 0


4 4 10 0
0 1
1 3
0 2
2 3
4



두 번째 예시의 경우이다.(각 도로에 붙은 번호는 입력된 순서이다.)
첫 번째 트럭이 0→1→3→4로 이동한다.
0번 도로(0-1간의 도로)를 수리한다.
두 번째 트럭이 0→1→2→4로 이동한다. 이 경우 트럭의 내구도 피해는 없다.

세 번째 예시의 경우이다. 0번부터 3번까지 10대의 트럭을 이동시켜야 하며, 도로 수리는 불가능하다.
다섯 대의 트럭이 0→1→3으로 이동하고,

나머지 다섯 대가 0→2→3으로 이동하면 된다. 이 경우 각 경로별로 마지막으로 이동한 트럭은 4의 부식도를 가진 도로만을 지나게 되며, 따라서 4의 내구도 손상을 입은 트럭 2대가 생긴다. 따라서 4를 출력한다.






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