Analysis: Milk Scheduling by Travis Hance
#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", ×[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; }