## 10989 - Bomb, Divide and Conquer

Moderator: Board moderators

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

### 10989 - Bomb, Divide and Conquer

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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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 :(

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

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..

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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
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
Contact:
There is a faster randomized algorithm for this problem, finding mincut from a graph.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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
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
Contact:
look up Karger's algorithm

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
I got AC at last, thanks everyone

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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
Abednego wrote:The time limit was 3 seconds.
I'm down to 2.870

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
misof wrote:I'm down to 2.870