Page 1 of 2
10989 - Bomb, Divide and Conquer
Posted: Wed Jan 25, 2006 2:19 am
by FAQ
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
Posted: Wed Jan 25, 2006 2:28 am
by Abednego
The statement means
Code: Select all
What is the minimum cut of the graph?
You tried max flow? Between which pair(s) of vertices?
TLE now :(
Posted: Wed Jan 25, 2006 3:13 am
by FAQ
Now I tried all pairs (i, j) (i <> j) then TLE instead :'(
maxflow mincut
Posted: Wed Jan 25, 2006 3:15 am
by wook
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 ,..........
Posted: Wed Jan 25, 2006 6:01 am
by Abednego
Yes, that would work, but I hope that it times out. :-)
Posted: Wed Jan 25, 2006 8:10 am
by FAQ
That's exactly what I tried but it's TLE, I wondered if we could do it better
Posted: Wed Jan 25, 2006 9:53 pm
by sclo
There is a faster randomized algorithm for this problem, finding mincut from a graph.
Posted: Thu Jan 26, 2006 3:12 pm
by little joey
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.
Posted: Thu Jan 26, 2006 4:27 pm
by wook
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?
Posted: Sat Jan 28, 2006 1:20 pm
by sclo
look up Karger's algorithm
Posted: Sat Feb 04, 2006 8:07 am
by FAQ
I got AC at last, thanks everyone
Posted: Tue Feb 14, 2006 12:02 pm
by misof
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
Posted: Tue Feb 14, 2006 4:32 pm
by Abednego
The time limit was 3 seconds.
Posted: Tue Feb 14, 2006 7:34 pm
by misof
Abednego wrote:The time limit was 3 seconds.
I'm down to 2.870
Posted: Wed Feb 15, 2006 8:59 am
by Cho
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.