### 10480 - Sabotage

Posted:

**Fri Aug 22, 2003 3:57 am**I want to use search but I think it's inefficient. Is there any efficient and

easy algorithm? Any hint is aprreciated.

easy algorithm? Any hint is aprreciated.

Page **1** of **1**

Posted: **Fri Aug 22, 2003 3:57 am**

I want to use search but I think it's inefficient. Is there any efficient and

easy algorithm? Any hint is aprreciated.

easy algorithm? Any hint is aprreciated.

Posted: **Fri Aug 22, 2003 8:30 am**

Max-flow min-cut, look it up..

Posted: **Mon Aug 25, 2003 10:59 am**

I know Max-flow, but it only calculates the minimum number of edges

to cut. How can I know the minimum cost?

to cut. How can I know the minimum cost?

Posted: **Tue Feb 13, 2007 3:18 am**

Does anyone have any test cases for this problem? It seems like it's just straight forward min-cut.

Thanks!

Code: Select all

```
Snip
```

Posted: **Tue Feb 13, 2007 4:36 am**

Here's some test cases that I came up with. The solutions to these are not necessarily unique.

Input:
Output:

Input:

Code: Select all

```
5 8
1 4 30
1 3 70
5 3 20
4 3 5
4 5 15
5 2 10
3 2 25
2 4 50
5 8
1 4 30
1 3 70
5 3 20
4 3 5
4 5 15
5 2 10
3 2 25
2 4 50
7 8
1 3 1
1 4 2
1 5 2
3 6 2
4 6 1
5 7 1
6 2 2
7 2 2
4 5
1 3 1
1 4 2
3 4 1
3 2 2
4 2 1
4 5
1 3 1
1 4 3
3 4 1
3 2 2
4 2 1
4 5
1 3 1
1 4 4
3 4 1
3 2 2
4 2 2
7 8
1 3 10
3 4 3
3 5 3
3 6 3
4 2 4
5 7 4
6 7 4
7 2 4
5 4
1 3 10
1 2 20
1 5 30
1 4 40
0 0
```

Code: Select all

```
1 4
3 2
3 4
3 5
1 4
3 2
3 4
3 5
1 3
4 6
5 7
1 3
1 4
1 3
4 2
4 3
1 3
4 2
4 3
3 4
7 2
1 2
```

Posted: **Sun Mar 13, 2011 12:30 am**

Use the cost as the capacity for each edge.sharklu2000 wrote:I know Max-flow, but it only calculates the minimum number of edges

to cut. How can I know the minimum cost?

Posted: **Sun Sep 18, 2011 8:03 am**

Data set for this problem is weak,I think.As,The Graph is undirected.

Output for following should be:

My latest accepted approach Outputs:
But my another accepted(Not supposed to get accepted ) outputs:
which is definitely wrong.

Output for following should be:

Code: Select all

```
7 7
1 4 2
4 5 5
5 2 2
1 7 3
7 5 3
4 6 3
6 2 3
0 0
```

My latest accepted approach Outputs:

Code: Select all

```
1 4
1 7
```

Code: Select all

```
1 4
5 4
5 2
```

Posted: **Tue Feb 05, 2013 12:21 pm**

This is the second problem I solved after learning flow algorithm. After figuring out that max flow is equivalent to min cut, the difficult part was finding a way to print the cuts. Read few books but it didn't help. Took me 3 days to find the following link. Hope it helps some one.

http://stackoverflow.com/questions/4482 ... -algorithm

http://stackoverflow.com/questions/4482 ... -algorithm

Posted: **Tue Feb 17, 2015 9:35 am**

Hmmm~~, how about the stategy above?