You are not logged in. Please login at www.codechef.com to post your questions!

×

Electric Town- Editorial

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

cg11's gravatar image

1★cg11
-54
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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