← All solutions

Shortest judge solution: 1649 bytes. Shortest team solution (during contest): 5492 bytes.

Python solutions by the judges: only Pypy

Even though the problem does its best to avoid using the word “flow”, it should be pretty clear that this is in fact a maximum flow problem, though it has a few twists to resolve. First, the viscosity parameter v is a red herring that is pretty much irrelevant to the problem and we will ignore it here.

A first small observation is that the desired flow will be a maximum flow from the water and Flubber sources to the destination. Let Z be that total maximum flow. Assume for the moment that it was possible to distribute this arbitrarily between Flubber and water, so that it was possible to route any amount F of Flubber between 0 and Z and W = Z − F water. Then a bit of calculus (left as an exercise) shows that the maximum flow would pick F = a · Z.

There are two different reasons why the assumption made above might not hold. One is a “trivial” one: the maximum amount of Flubber routable from Flubber source to destination might be less than a · Z, or the amount of water routable might be less than (1 − a) · Z. If this is the case, we should simply set the desired amount of Flubber F to value nearest to a · Z in the interval [Z − W_max, F_max]. Let us refer to the resulting potentially optimal values of F and W as F ∗ and W ∗ = Z − F ∗.

The second reason is a bit more subtle – it is not clear whether it is the case that we can simultaneously achieve Flubber F ∗ and water W ∗. Let ~f₁ be a flow which routes F_max Flubber and Z − F_max water, and let ~f₂ be a flow which routes Z − W_max Flubber and W_max water. Then for α ∈ [0, 1], α ~f₁ + (1 − α) ~f₂ is a flow of fluids in which αF_max + (1 − α)(Z − W_max) of the fluid originates at the Flubber source, and we can set α appropriately to a constant so that this equals F ∗. However, there is a snag with this: there might be pipes where ~f₁ and ~f₂ route fluids in opposite directions, so it is not clear that we can achieve this flow while satisfying the “water and Flubber must not go in opposite directions” constraint. Phrased a bit more abstractly, the “no opposing flows” constraint is not a convex constraint.

It turns out that this second reason is actually a non-reason – it is always possible to achieve Flubber F ∗ and water W ∗. But we now have to construct the actual Flubber and water flows. One way of doing that is to take the mixed flow ~f^∗ := α ~f₁ + (1 − α) ~f₂ from above. This tells us how much fluid we would like to send (and in which direction) along each pipe, but it doesn’t tell us how much of that fluid should be Flubber, and how much should be water. To figure that out, we make a new flow graph where we set the (directed) capacity of each edge to be the (directed) flow in ~f^∗ along that edge. We then compute the maximum flow from the Flubber source in the new graph. This gives the Flubber flow, and the unused capacity gives the water flow. An issue here is that the new graph has non-integer capacities, so one may have to be a bit careful when computing the maxflows.