# Maximum flow on a n ×n grid

I am currently dealing with a network flow problem and I am trying to find some similar solved problems to help me formulate my solution.

The text is:

You are the owner of a large chain of franchise shops, and you would like to expand to a new city. The blocks in your city make an $$n ×n$$ grid. However, although your products are awesome and in high demand, the city will not allow you to open a shop in each block. Instead, for every row of blocks i, you are are given a number $$r_i$$ that limits the maximum number of shops opened there - and for every column j, there also is a maximum number $$c_j$$ .

a) Find the maximum number of franchise shops you can legally open in the city. To do so, model the problem as a flow network. Then, describe how to get the right answer using Ford-Fulkerson, and prove the correctness of your construction.

How can I construct the digraph from the $$n ×n$$ grid ? I think the blocks can be represented in this way grid Should I assume an initial orientation on the grid?

Assume an $$n\times n$$ grid. I'd build a network as follows. A source on the left with $$n$$ arcs going to $$n$$ nodes each representing a row of the grid. Call these $$n$$ nodes $$R_1, R_2...R_n$$. The flow capacity on the $$i^{th}$$ arc (from source to $$R_i$$) is $$r_i$$. Do something similar at the sink. Have arcs arriving there from nodes $$C_1,C_2..C_n$$ with capacity $$c_i$$. Then connect each $$R_i$$ to $$C_j$$ with an arc of capacity 1. Maximize the flow. The arcs $$R_i-C_j$$ chosen to have a flow in an optimal solution will tell you to place a franchise at grid point $$i,j$$.
• Well there are $n^2$ paths. That is, every node of the grid corresponds to a path. So you can only pick them all if your $r_i$ and $c_i$ are at least $n$. But for the general case, the flows will be maximal subject to those constraints and will pick out the max number of grid points that are feasible. Nov 23 at 14:02
• Assuming a full 3x3 grid, you're missing 6 arcs in the middle ($R_1$ to $C_2$, $R_1$ to $C_3$, $R_2$ to $C_1$.......) So each point of the grid (say in row $i$ and column $j$) corresponds to an arc from $R_i$ to $C_j$. Nov 23 at 14:33
• Ok thank you but I don't get the capacity of 1. For example: in the path S-->$R_1$-->$C_1$-->T the minimum capacity is 1 so for every arcs flows exactly 1 (1/$r_1$,1,1/$c_1$) and so on for the others. Nov 23 at 14:51