Subtask 1

For the first subtask, we can think of the movement of acorns as a flow network. We can create edges from the source node to each of the nodes representing the ~M~ trees with a capacity equal to ~f_j~. We can then add edges from each of the nodes representing the ~N~ squirrels to the sink node with a capacity equal to ~b_i~. Finally, we can add edges from the ~j^{th}~ tree to the ~i^{th}~ squirrel with a capacity equal to ~d_{ij}~. We can run a maximum flow algorithm on the graph to determine the maximum acorns that need to be collected. The minimum is always ~0~. The squirrels will always survive the quarantine without wasting food if ~0~ acorns are produced and consumed.

Time Complexity: ~\mathcal{O}((N + M)^3)~ if the Push-Relabel algorithm is used, though efficient Dinic and Edmonds Karp implementations should both pass within the time limit.

Subtask 2

For the second subtask, we can think of ~a_i~, ~c_{ij}~, and ~e_j~ as minimum demands for the edges in the flow network. While there are methods to handle the demands for this specific structure of the graph, we can also use a more general method by first finding any feasible flow. First, we can create a new flow network with a new source and sink. We add an edge from the new source to every vertex in the original graph with a capacity equal to the sum of demands of all outgoing edges from that vertex in the old graph. We add an edge from each vertex to the new sink with a capacity equal to the sum of the demands of all incoming edges to that vertex in the old graph. We add an edge between each pair of vertices where there existed an edge between that pair in the old graph, with a capacity equal to the demand subtracted from the old capacity. Finally, an edge is added from the old sink to the old source with an infinite capacity. After running the maximum flow on the new graph, we can determine if there is a feasible flow in the old graph by determining if every outgoing edge from the new source has a residual capacity of ~0~. The value of the feasible flow can be found by looking at the flow on the edge from the old sink to the new source.

To determine the max flow, we can run the maximum flow algorithm on the residual graph after finding the feasible flow (using only the original edges) and adjusting the edges for the subtracted demand. Remember to add the value of the feasible flow.

To find the minimum flow, we can observe that if we lower the capacity of the edge from the old sink to the new source, eventually, there will be no feasible solution. We can binary search for the value of this edge in order to determine the minimum capacity of this edge, where a feasible flow exists, which is also equal to the value of the minimum flow.

Let ~K = \sum_{i=1}^N b_i~.

Time Complexity: ~\mathcal{O}((N + M)^3 \cdot \log K)~ if the Push-Relabel algorithm is used, though an efficient Dinic implementation should pass within the time limit.