10480 - Sabotage

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

Moderator: Board moderators

Post Reply
sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

10480 - Sabotage

Post by sharklu2000 » 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.

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Fri Aug 22, 2003 8:30 am

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

sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by sharklu2000 » 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?

Kevin
New poster
Posts: 7
Joined: Tue Oct 24, 2006 2:14 am

10480 - test cases?

Post by Kevin » 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.

Code: Select all

Snip
Thanks!

Kevin
New poster
Posts: 7
Joined: Tue Oct 24, 2006 2:14 am

Post by Kevin » 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:

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

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


DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re:

Post by DD » Sun Mar 13, 2011 12:30 am

sharklu2000 wrote:I know Max-flow, but it only calculates the minimum number of edges
to cut. How can I know the minimum cost?
Use the cost as the capacity for each edge.
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10480 - Sabotage

Post by Imti » 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:

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
But my another accepted(Not supposed to get accepted :D) outputs:

Code: Select all

1 4
5 4
5 2
which is definitely wrong.

forthright48
New poster
Posts: 37
Joined: Wed Mar 14, 2012 11:57 am
Location: Bangladesh
Contact:

Re: 10480 - Sabotage

Post by forthright48 » 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
What ever happens, happens for good. Even when we get WA :p
http://www.forthright48.com


Post Reply

Return to “Volume 104 (10400-10499)”