철도망의 운영을 맡고 있다. 이 철도망은 \mathbf{N}개의 역으로 이루어진다. 각 역 i는 정확히 한 개의 다른 역 \mathbf{D_i}로 물품을 보내야 한다. 역 i는 정확히 한 번의 배송을 수행하며, 정확히 \mathbf{C_i}개의 철도 차량(칸)을 가진 열차를 보내야 한다.

모든 배송 정보를 충분히 미리 알 수 있으므로, 철도 차량을 재사용해서 필요한 차량 수를 줄이려 한다. 역 i가 역 \mathbf{D_i}로 철도 차량 n개를 보내면, 역 \mathbf{D_i}는(아직 자신의 배송을 보내기 전이라면) 그 차량들을 자신의 공급량에 더해 자신의 배송에 사용할 수 있다.

정확히 말해, 각 역에 초기 철도 차량 공급량을 지정해야 한다(어떤 역은 0개를 받아도 된다). 또한 배송들을 수행할 순서를 정해야 한다. 그렇게 해서 역 i가 배송을 보내야 하는 시점에는, 역 i에 대해 (초기 공급량과 이전에 도착한 배송들로부터 받은 차량 수를 합한 값)이 그 역이 필요로 하는 차량 수 \mathbf{C_i} 이상이어야 한다. 역 i에 \mathbf{C_i}보다 더 많은 차량이 있더라도, 역 i에서 나가는 배송에 \mathbf{C_i}개보다 더 많이 실어 보낼 수는 없다.

예를 들어, 역 1이 역 4로 정확히 철도 차량 3개를 실은 열차를 보낸다고 하자. 이제 역 4가 차량 2개가 필요하다면, 역 1에서 받은 차량 중 2개를 재사용할 수 있다. 또한 역 4가 차량 5개를 보내야 한다면, 역 1에서 받은 3개를 전부 재사용하고 자신의 초기 공급량에서 2개를 더해 보낼 수 있다. 하지만 역 4가 차량 2개만 보내야 할 때에는, 역 1에서 받은 3개를 전부 보낼 수는 없다는 점에 주의하라.

배송 정보가 주어질 때, 어떤 순서로든 모든 배송을 수행할 수 있도록 하려면 각 역에 초기 공급량으로 나누어 주어야 하는 철도 차량의 최소 총개수는 얼마인가?

#10457 upload 1 done 1 how_to_reg 1

철도 운영 timer 40s memory 2048MB

#10457

철도 운영 40s 2048MB