P3074 [USACO13FEB] Milk Scheduling S

Farmer John has $N$ cows ($1 \leq N \leq 10^4$), numbered from $1$ to $N$. Milking cow $i$ takes $T_i$ units of time. Due to the barn layout, some cows must finish milking before others can start. For example, if cow $A$ must be milked before cow $B$, then cow $A$ must be completely milked before starting cow $B$. To finish as quickly as possible, John has hired many workers and can milk any number of cows simultaneously. However, the precedence constraints must still be respected. Compute the minimum total time to finish all milking.

- The first line: two integers $N$ (number of cows) and $M$ (number of constraints, $1 \leq M \leq 5\times 10^4$). - Lines $2$ through $N+1$: each line contains one integer $T_i$, the milking time of cow $i$ ($1 \leq T_i \leq 10^5$). - Lines $N+2$ through $N+M+1$: each line contains two integers $A$ and $B$, meaning cow $A$ must be completely milked before starting cow $B$. All constraints are acyclic, so a solution is guaranteed.

- One line: the minimum total time to complete all milking.

There are $3$ cows with milking times $10, 5, 6$. Cow $3$ must finish before cow $2$. Initially, cows $1$ and $3$ can be milked simultaneously (taking $10$ and $6$). After cow $3$ finishes, start cow $2$ (total time $6 + 5 = 11$). Translated by ChatGPT 5