Hi Codeforces,

I'm currently working on a problem related to network flows. Does anyone know how to implement constraints of the following type into a system? Edges 1 and 2 go into the vertex, and have capacity one. Edges 3 and 4 go out and have capacity one. How can one force a constraint to the effect of (edges 3 and 2 can't have a sum of flows greater than one)? UPD: I should note the context involves min-cost flow, so perhaps we can leverage the costs of the edges.

Split the vertex in two, A and B.

Edge 1 goes into A, edges 3 goes out of A, edge 2 goes into B, edge four goes out of B, there's an edge from A to B with infinite capacity.

So I can send 1 into A via edge1, 1 going out of A via edge3; 1 into B via edge2, 1 out of B via edge4.

Now flow sum of edge2 and edge3 is 2, right?

Yes, you are right.

Then I have no idea how to do this :)

Auto comment: topic has been updated by Franklyn_W (previous revision, new revision, compare).I'm not sure if I understood the constraint correctly but I think it is easy to construct a system with this constraint where the (unique) optimal solution is non-integral. Therefore it is not likely that there exists a straightforward reduction to min-cost flow. (if a reduction exists it should multiply all capacities/weights with something).