StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>It is a graph theory <code>maximum flow</code> problem.</p> <p>Suppose that every circle is a node in the graph. Additionally introduce 2 special nodes: <code>TOP</code> and <code>BOTTOM</code>. Connect circles with these nodes if they intersect with TOP/BOTTOM side. Connect nodes corresponding to circles with each other if the circles intersect.</p> <p>Now you need to find a minimum cut in this graph, having <em>TOP as source</em> and <em>BOTTOM as sink</em> or vice versa. You can use <a href="http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem" rel="noreferrer">Max-flow_min-cut_theorem</a> to solve it. What it states is that <code>Minimum-cut problem</code> is equivallent to Max-flow problem. You can find details on how to solve <code>Max-Flow problem</code> on <a href="http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=maxFlow" rel="noreferrer">TopCoder</a>.</p> <p>As we can go through each node only once, we should convert the nodes into a directed edge of capacity one with in-node and out-node for each circle. The max-flow algorithm will solve the problem on the resulting graph and take into account the fact that we are removing circles rather than connections between circles. It is always a better decision for this problem to remove a node in a graph rather than edge, as we can always remove any edge by removing a node. Removing a node additionally can result in removing more than one edge. </p> <p>By the way, a similar problem can be found on <a href="http://uva.onlinejudge.org/external/118/11853.html" rel="noreferrer">Uva Online Judge</a>. It a good idea to try solve this task on the judge, then you will be sure that your solution is correct.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload