Say you have n sources s1, ..., sn with source capacities ci and m sinks t1, ..., tm. Let f = sumi ci. We want to find a feasible flow in the network where every source i has a net flow of -ci and every sink has a net flow of f / m.
We can solve this by introducing a super source S and a super sink T and connecting each of the sources i to S via an edge (si, S) of capacity ci. We connect each ti to T via an edge of capacity f / m. Then we just run max-flow with source S and sink T.
If it is not possible to push exactly f / m units of flow to each sink, it is not clear what you want to optimize, but you might find the following two approaches useful:
- Choose e and connect the sinks to T via edges with capacities f / m + e. Use binary search to find the minimum e such that the total flow will be f. This minimizes maxi inflow(ti)
- Choose e and add the sinks to T via edges with lower bound e. Use binary search to find the maximum e that still allows for a feasible flow. This maximizes mini inflow(ti). The feasible flow problem with lower bounds can be reduced to max-flow: http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf In this case the construction is really simple: Just add an additional super-source S' and connect S' to S via an edge of capacity m * e. Connect all sinks to T via edges of capacity e. Check if the maximum flow between S' and T is m * e