001package algs44; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac CPM.java 005 * Execution: java CPM < input.txt 006 * Dependencies: EdgeWeightedDigraph.java AcyclicDigraphLP.java StdOut.java 007 * Data files: http://algs4.cs.princeton.edu/44sp/jobsPC.txt 008 * 009 * Critical path method. 010 * 011 * % java CPM < jobsPC.txt 012 * job start finish 013 * -------------------- 014 * 0 0.0 41.0 015 * 1 41.0 92.0 016 * 2 123.0 173.0 017 * 3 91.0 127.0 018 * 4 70.0 108.0 019 * 5 0.0 45.0 020 * 6 70.0 91.0 021 * 7 41.0 73.0 022 * 8 91.0 123.0 023 * 9 41.0 70.0 024 * Finish time: 173.0 025 * 026 *************************************************************************/ 027 028public class CPM { 029 030 public static void main(String[] args) { 031 StdIn.fromFile ("data/jobsPC.txt"); 032 033 // number of jobs 034 int N = StdIn.readInt(); 035 036 // source and sink 037 int source = 2*N; 038 int sink = 2*N + 1; 039 040 // build network 041 EdgeWeightedDigraph G = new EdgeWeightedDigraph(2*N + 2); 042 for (int i = 0; i < N; i++) { 043 double duration = StdIn.readDouble(); 044 G.addEdge(new DirectedEdge(source, i, 0.0)); 045 G.addEdge(new DirectedEdge(i+N, sink, 0.0)); 046 G.addEdge(new DirectedEdge(i, i+N, duration)); 047 048 // precedence constraints 049 int M = StdIn.readInt(); 050 for (int j = 0; j < M; j++) { 051 int precedent = StdIn.readInt(); 052 G.addEdge(new DirectedEdge(N+i, precedent, 0.0)); 053 } 054 } 055 056 // compute longest path 057 AcyclicLP lp = new AcyclicLP(G, source); 058 059 // print results 060 StdOut.println(" job start finish"); 061 StdOut.println("--------------------"); 062 for (int i = 0; i < N; i++) { 063 StdOut.format("%4d %7.1f %7.1f\n", i, lp.distTo(i), lp.distTo(i+N)); 064 } 065 StdOut.format("Finish time: %7.1f\n", lp.distTo(sink)); 066 } 067 068}