10989 - Bomb, Divide and Conquer

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

10989 - Bomb, Divide and Conquer

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

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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?
If only I had as much free time as I did in college...

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

TLE now :(

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

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

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

maxflow mincut

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 ,..........
Sorry For My Poor English.. :)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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

Yes, that would work, but I hope that it times out. :-)
If only I had as much free time as I did in college...

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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

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

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

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.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

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?
Sorry For My Poor English.. :)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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

look up Karger's algorithm

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm

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

I got AC at last, thanks everyone :)

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

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 :)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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

The time limit was 3 seconds.
If only I had as much free time as I did in college...

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

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

Abednego wrote:The time limit was 3 seconds.
I'm down to 2.870 :)

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

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.

Post Reply

Return to “Volume 109 (10900-10999)”