### Franklyn_W's blog

By Franklyn_W, history, 7 years ago,

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.
• +8

| Write comment?
 » 7 years ago, # |   0 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.
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ |   0 Yes, you are right.Then I have no idea how to do this :)
 » 7 years ago, # |   0 Auto comment: topic has been updated by Franklyn_W (previous revision, new revision, compare).
 » 7 years ago, # |   0 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).