10989 - Bomb, Divide and Conquer

FAQ · Post by **FAQ** » Wed Jan 25, 2006 2:19 am

Could anyone explain this sentence to me please?

What is the minimum total cost of bombing enough roads to ensure that there is some pair of cities that have no path between them? A path is a sequence of connected roads.

I tried normal MaxFlow MinCut and WA :'(, so maybe I misunderstood the statement

Abednego · Post by **Abednego** » Wed Jan 25, 2006 2:28 am

The statement means

Code: Select all

What is the minimum cut of the graph?

You tried max flow? Between which pair(s) of vertices?

FAQ · Post by **FAQ** » Wed Jan 25, 2006 3:13 am

Now I tried all pairs (i, j) (i <> j) then TLE instead :'(

wook · Post by **wook** » Wed Jan 25, 2006 3:15 am

just for pair (1, i), 2<=i<=n

S <- pick up any vertex in V
foreach T in V, S ≠ T
......... m[T] <- maximum_flow(S, V, G)

and, then the minimum-cut is min{ m[T] | T ∈ V, S ≠ T}.

so there can be a O(V^4) algorithm, maybe ,..........

Abednego · Post by **Abednego** » Wed Jan 25, 2006 6:01 am

Yes, that would work, but I hope that it times out. :-)

FAQ · Post by **FAQ** » Wed Jan 25, 2006 8:10 am

That's exactly what I tried but it's TLE, I wondered if we could do it better

sclo · Post by **sclo** » Wed Jan 25, 2006 9:53 pm

There is a faster randomized algorithm for this problem, finding mincut from a graph.

little joey · Post by **little joey** » Thu Jan 26, 2006 3:12 pm

sclo wrote:There is a faster randomized algorithm for this problem, finding mincut from a graph.

Did you get accepted with that? AFAIK the randomised algorithm only gives an approximation.

Great problem, Igor (and great problemset in general). Learned a new algorithm. Just out of curiosity: can this algorithm be adapted to identify the partition(s) of a mincut (in terms of broken edges)?

Edit: stupid question; of course it can.

wook · Post by **wook** » Thu Jan 26, 2006 4:27 pm

I can't think of very efficient method for this problem.
yes, a general maximum-flow minimum-cut algorithm is too slow!

how faster should I make it?

sclo · Post by **sclo** » Sat Jan 28, 2006 1:20 pm

look up Karger's algorithm

FAQ · Post by **FAQ** » Sat Feb 04, 2006 8:07 am

I got AC at last, thanks everyone

misof · Post by **misof** » Tue Feb 14, 2006 12:02 pm

Abednego: Just for your reference, yesterday I managed to get AC in 4.5 seconds, using Dinic's maxflow algorithm to find the minimum cut between all pairs [1,x]. Of course, I don't really know what was the time limit in the real contest

Abednego · Post by **Abednego** » Tue Feb 14, 2006 4:32 pm

The time limit was 3 seconds.

misof · Post by **misof** » Tue Feb 14, 2006 7:34 pm

Abednego wrote:The time limit was 3 seconds.

I'm down to 2.870

Cho · Post by **Cho** » Wed Feb 15, 2006 8:59 am

misof wrote:I'm down to 2.870

I've tried the same approach after reading your post, but TLE.
Could you tell me whether you use the same maxflow routine as your 10983 (Buy one, get the rest free) to solve this problem?

[EDIT:] AC now, by Stoer and Wagner's algorithm.

OJ Board

10989 - Bomb, Divide and Conquer

10989 - Bomb, Divide and Conquer

TLE now :(

maxflow mincut