OJ Board

Could anyone tell me efficient algorithm to solve this problem ?

(Problem H - Sabotage)
For given graph find minimum cost of edges (and print this edges), which must be eliminated from graph, in such way, that graph split to two parts.
In problem says that one part must contains vertex 1, and second - vertex 2, but I think, that it's not important which vertex is in which part of graph.

Maybe someone tell me name of this algorithm or give me a link to implementation or site with more information about it ?

Thanks for help
Dominik Michniewski

Hi!


Yes these kind of problems are quite interesting (and difficult...)
but about the algorithm :

1. The value of paths, you will have to cut is equal to maximum flow in this graph. ( you consider edges as they have capacity equal to their cost, I hope you understood this

2. Now we check which nodes we can reach from the beginning ( in our new graph, after counting the maximum flow, and we consider the edges only with positive (non zero) value )

3. For each edge if its value = 0 and it goes from the node we can reach from the beginning (the 2 point above ) to the node, we cannot, we consider this edge as a part of our solution... ==> this is the edge we have to cut ..


And that's all..

I hope you understood

Good Luck

The value you looking for is called "Minimum cut". Search google for these word "minimum cut flow" . There's heap of !
Cheers

Thanks cyfra, I finaly got it.
Although your description is a little crooked (that's not your fault, but your English is a tad weak ), it helped me more than spending two hours with google.
All those web sites telling you how simple it is, going into lengthy explanations how to find the max flow, but stopping just short of explaining how to find the actual min cut .
It's not easy if you are just an amateur without an education in CS to find the right sources, especialy for graph problems. So if anyone knows of a good book on graph theory (beyond Cormen, but without too much mathematical mambo-jambo) that I could use, please tell me.

I don't remember off my head if this book contains precisely what you're looking for, but I find it to be a good CS-oriented Graph Theory book (as opposed to pure math ones I've read..)

It's Sedgewick's Algorithm in C, Part 5, Graph Theory, with ISBN of 3D0201316633.