Problem Link : Contest Practice Difficulty : Medium Prerequisites : 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, 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
This gives us the original flow formulation. Setter's code : code asked 25 Oct '14, 20:42
