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).