(5 points) You are asked to fill in an nn matrix with non-negative integer values subject to the following constraints. The sum of the i th row must be ri, and the sum of the i th column must be ci. Note that i=1nri=i=1nci as both values represent the sum of all of the entries. The (i,j) th entry can be no more than ai,j. (a) Describe how to represent this situation as a network flow problem. Hint: Create a vertex for each row and a vertex for each column. (b) Let A,B be the minimum st cut such that sA and tB in your solution from the previous part. Assume that it is not possible to fill in the matrix subject to these constraints. Describe how to use this to determine a proof of this, of the following form. There exist a set of columns C and a set of rows R such that jCcjiRri+i/R,jCai,j That is, the sum of the row sums in R plus the sum of the maximum values in for entries in columns in C but not in the rows R, is less than the sum of the column sums in C. For example, consider the following matrix of maximum values 334412311 and assume that r1=3,c2=5,c3=4. Then it is not possible to fill in the matrix satisfying the constraints of this problem, by taking R={1} and C={2,3}