**Problem Link : **
[Contest][1]
[Practice][2]
**Difficulty : ** Medium
**Pre-requisites : ** Max flow
**Solution : **
Note that the problem is stated like a flow problem, where A is the source and B is the target. The flow in the single edge from B to A (with infinite capacity) is to be maximized.
The only thing different from a flow problem is that instead of the equality condition at every node (S = R, in terms of the problem), we are given (S = R + G), where G ≥ 0. However, the condition must hold for every node, so that for every node we have,
Incoming flow ≤ Outgoing flow
=> Total incoming flow ≤ Total Outgoing flow (total meaning we sum over all nodes)
But every edge corresponds to an equivalent amount of incoming and outgoing flow contributed to the above inequality. Thus, total incoming flow = total outgoing flow. Hence, we must have equalities everywhere, giving for every node:
Incoming flow = Outgoing flow
=> For every node, S = R, or G = 0.
This gives us the original flow formulation.
**Setter’s code : **
[3]
[1]: http://www.codechef.com/WPC1401/problems/IITK1P04
[2]: http://www.codechef.com/problems/IITK1P04
[3]: http://www.codechef.com/viewsolution/4942762