Contest02-6 Flows in Grid
The maximum flow problem in general graph is so hard that bob doesn't know how to solve it. So bob wants to try an easy one, the maximum flow in grid. But this easier one is still too hard for bob. Now here is his problem, please help him:
Given you a N*M grid as followed, edges of the grid represent pipes which the water can run through; the number of the edge is the capacity of the pipe. For example in Figurn 1 the capacity of the edge between (0,0) and (1,0) is 6, it means that at most 6 units of water can run through this edge(pipe).
So what is the maximum flow from S to T in the grid? In other words, at most how many units of water can run through from S to T at a time?
The first line of each test case is two positive integers N(1 < N < 100)and M(1 < M < 100). And then two integer matrices H(N*(M-1)) and V((N-1)*M) follow. H[i][j] is the capacity of the edge between(i,j) and (i,j+1). V[i][j] is the capacity of the edge between (i,j) and (i+1,j). All integers in H and V are non-negative and smaller than 10^10.
1 3 3 0 1 2 3 4 5 6 7 8 9 10 11