Analysis: Milk Scheduling by Travis Hance

Since we can milk as many cows as we want in parallel, it never hurts to start milking a cow as soon as possible, that is, as soon as all the cows it depends on have been milked. Thus, we just need to compute when we will finish if we milk all the cows using this greedy approach.

To compute the minimum time that a particular cow C will finish, we just need to find the maximum of among all minimum finish times of the cows that C depends on, and add that to the time it takes to milk cow C. Since we need to compute the times for all the cows, we just need to resolve the cows in the correct order.

There are a number of ways to do this. The most direct way is to topological sort on all the cows first, and then resolve them in that order. To save coding time, we don't need to explicitly sort the cows though. One approach is to do the following: whenever we want to compute the time for a cow, we check all of that cow's dependencies. If any of them have not yet been computed, then we recursively compute those. This is the approach taken in the C++ solution below. Alternatively, we could use a queue to keep track of which cows we are able to compute the times for; then, each time we compute the time for a cow, we check if any of the cows depending on it can now be computed, and if so, we append them to the queue. This is the approach taken in the Java solution.

Here is the C++ solution: 
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define NMAX 10005

long long times[NMAX];
vector<int> dependencies[NMAX];
long long minfinishtime[NMAX];

// Returns the minimum finish time for cow i,
// computing the value if it has not yet been computed.
long long get_minfinishtime(int i) {
    if (minfinishtime[i] == -1) {
        long long start = 0;
        for (int j = 0; j < dependencies[i].size(); j++) {
            start = max(start, get_minfinishtime(dependencies[i][j]));
        }
        minfinishtime[i] = start + times[i];
    }
    return minfinishtime[i];
}

int main() {
    freopen("msched.in","r",stdin);
    freopen("msched.out","w",stdout);

    // input
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &times[i]);
        minfinishtime[i] = -1;
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        dependencies[b].push_back(a);
    }

    // find the maximum among all minimum times
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, get_minfinishtime(i));
    }
    printf("%d\n", ans);
}
And here is Jonathan Paulson's solution in Java: 
import java.util.*;
import java.io.*;
import java.awt.Point;
import static java.lang.Math.*;

public class msched {
    public static int i(String s) { return Integer.parseInt(s); }
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new FileReader("msched.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new
FileWriter("msched.out")));
        String[] arr = in.readLine().split(" ");
        int n = i(arr[0]);
        int m = i(arr[1]);

        // input
        C = new int[n];
        for(int i=0; i<n; i++) {
            C[i] = i(in.readLine());
        }

        int[] D = new int[n];
        List<List<Integer>> E = new ArrayList<List<Integer>>();
        for(int i=0; i<n; i++) E.add(new ArrayList<Integer>());
        for(int i=0; i<m; i++) {
            arr = in.readLine().split(" ");
            int x = i(arr[0])-1;
            int y = i(arr[1])-1;
            E.get(x).add(y);
            D[y]++;
        }

        // initialize queue with cows that can start immediately.
        Queue<int[]> Q = new PriorityQueue<int[]>(10,
            new Comparator<int[]>() {
                public int compare(int[] A, int[] B) {
                    return A[1]-B[1];
                }
            });
        for(int i=0; i<n; i++)
            if(D[i]==0) {
                Q.add(new int[]{i, C[i]});
            }

        // compute times for all cows
        int ans = 0;
        while(!Q.isEmpty()) {
            int[] e = Q.poll();
            int x = e[0];
            int t = e[1];
            ans = Math.max(ans, t);
            for(Integer y:E.get(x)) {
                D[y]--;
                if(D[y] == 0) {
                    Q.add(new int[]{y, C[y]+t});
                }
            }
        }

        out.println(ans);
        out.flush();
    }
    static int[] C;
}