레이팅 미적용농부 존(Farmer John)의 N마리 (1 <= N <= 10,000) 소들은 편의상 1..N으로 번호가 붙어 있다. 각 소 i의 젖을 짜는 데는 T(i) 단위의 시간이 걸린다. 안타깝게도 FJ의 헛간 구조 때문에, 어떤 소들은 다른 소들보다 먼저 젖을 짜야 한다. 소 A를 소 B보다 먼저 짜야 한다면, FJ는 A의 착유를 완전히 끝낸 후에야 B의 착유를 시작할 수 있다.
소들의 젖을 최대한 빨리 짜기 위해, FJ는 많은 수의 일꾼을 고용했다. 몇 마리든 동시에 젖을 짤 수 있을 만큼 충분하다. 하지만 여러 소의 젖을 동시에 짤 수 있더라도, 특정 소를 다른 소보다 먼저 짜야 한다는 제약 때문에 전체 과정이 진행되는 속도에는 한계가 있다. 착유 과정에 걸리는 최소 총시간을 계산하는 것을 FJ에게 도와주자.
첫째 줄: 공백으로 구분된 두 정수 N (소의 수)과 M (착유 제약의 수; 1 <= M <= 50,000).
둘째 줄부터 1+N번째 줄까지: i+1번째 줄에 T(i)의 값 (1 <= T(i) <= 100,000)이 주어진다.
2+N번째 줄부터 1+N+M번째 줄까지: 각 줄에 공백으로 구분된 두 정수 A와 B가 주어지며, 소 A의 착유를 완전히 끝내야 소 B의 착유를 시작할 수 있음을 나타낸다. 이 제약들은 절대 순환을 이루지 않으므로, 해는 항상 존재한다.
모든 소의 젖을 짜는 데 필요한 최소 시간.
msched.in · 출력을 쓸 파일 msched.out3 1
10
5
6
3 211Output details: Cows 1 and 3 can be milked at the same time. When cow 3 finishes, cow 2 begins. All cows finish after 11 units of time.
riseoj 작성
출처 올림피아드 > USACO > 2012-2013 > February > Silver