MathCastle
Graph TheoryHardGraph Algorithms

Graph Algorithms · Hard problem

A project has tasks p,q,r,a,b,cp,q,r,a,b,c with durations (days) and prerequisites p→qp \to q (55), p→rp \to r (33), q→aq \to a (22), r→ar \to a (44), r→br \to b (66), a→ca \to c (33), b→cb \to c (11). Each number is how many days that task itself takes. By how many days does the whole project (ending at cc) shorten if task q→aq \to a's portion is cut from 22 days to 00 days?