Algorithm · Karat · Hard
A processing pipeline is modeled as a directed acyclic graph. Each node is a processing stage, and each stage has a capacity: the maximum amount of work that can pass through it. One node is marked as the source and another as the sink. Find the largest total throughput that can be sent from the source to the sink so that the amount of work passing through each stage never exceeds that stage's capacity. The source does not give the input format, the output format, any…