×

# Electric Town- Editorial

 0 Problem Link : Contest Practice 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 : code asked 25 Oct '14, 20:42 1★cg11 -5●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,655
×114
×58
×44
×1

question asked: 25 Oct '14, 20:42

question was seen: 729 times

last updated: 25 Oct '14, 20:42