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?

- Abednego
- 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 minimum-cut 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 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..

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