I tried normal MaxFlow MinCut and WA :'(, so maybe I misunderstood the statementWhat 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.
10989  Bomb, Divide and Conquer
Moderator: Board moderators
10989  Bomb, Divide and Conquer
Could anyone explain this sentence to me please?

 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
The statement means
You tried max flow? Between which pair(s) of vertices?
Code: Select all
What is the minimum cut of the graph?
If only I had as much free time as I did in college...
TLE now :(
Now I tried all pairs (i, j) (i <> j) then TLE instead :'(
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 minimumcut is min{ m[T]  T ∈ V, S ≠ T}.
so there can be a O(V^4) algorithm, maybe ,..........
S < pick up any vertex in V
foreach T in V, S ≠ T
......... m[T] < maximum_flow(S, V, G)
and, then the minimumcut is min{ m[T]  T ∈ V, S ≠ T}.
so there can be a O(V^4) algorithm, maybe ,..........
Sorry For My Poor English..

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Did you get accepted with that? AFAIK the randomised algorithm only gives an approximation.sclo wrote:There is a faster randomized algorithm for this problem, finding mincut from a graph.
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.