OJ Board

Cho wrote:

misof wrote:I'm down to 2.870

I've tried the same approach after reading your post, but TLE.
Could you tell me whether you use the same maxflow routine as your 10983 (Buy one, get the rest free) to solve this problem?

I had to play with optimizations to get this one. I have a pre-written maxflow, but it is in C++ and uses some STL (basically just a bunch of vectors). Of course, here at UVa the judge has an old g++, and compiles without the for-STL-necessary -O2, so this was quite a setback. This solution didn't pass even the 10 seconds time limit.

The first step was basically to rewrite it to plain C -- a global int G[][] instead of a vector< vector<int> > &G passed as a parameter, and such.

Other optimizations include:
- once the current flow exceeds your so-far-best cut, terminate it
- using a heuristic to get the first bound on the mincut (cutting off any one vertex)
- I fix a vertex v and search all pairs [v,w], I use an heuristic to choose v so that the above pruning is expected to be a bit more effective.\

One other optimization I didn't implement: run BFS first, and process the vertices w in decreasing distance order.

after readin the posts i come to know the names of some algos... can any one plz give me web addr to know about these algos? [i searched in yahoo but did not find much helpful links.]

Karger's algorithm
Dinic's maxflow algorithm
Stoer and Wagner's algorithm

Thanks in advance.

Mahbub

You'd better google them. Queries like "Karger min cut" will easily get you this link.

Good luck!

Thanks

I can't understand Dinic's algortihm. can any one please make me understand it through example?

hi everybody.
I've applied the Stoer-Wagner algo to find the min-edge-cut
but I'm getting WA!
I've tried any kind of test cases... (disconnected graph, containing bridge, complete graph, ....)
is there any tricky test data???
can any one give me some test data plz...
tnx in advance.

shanto86 wrote:after readin the posts i come to know the names of some algos... can any one plz give me web addr to know about these algos? [i searched in yahoo but did not find much helpful links.]

Karger's algorithm
Dinic's maxflow algorithm
Stoer and Wagner's algorithm

Thanks in advance.

Mahbub

read Stoer-Wagner algo + Karger-Stein algo here:
http://maagar.openu.ac.il/opus/Static/b ... s%5D_0.pdf
and here's a good step-by-step sample for stoer-wagner algo:
http://www.cs.dartmouth.edu/~rahul/Teac ... mincut.pdf

good luck.

I got AC using stoer wagner's algorithm! Thanks a lot nima!

nima101 wrote:

shanto86 wrote:after readin the posts i come to know the names of some algos... can any one plz give me web addr to know about these algos? [i searched in yahoo but did not find much helpful links.]

Karger's algorithm
Dinic's maxflow algorithm
Stoer and Wagner's algorithm

Thanks in advance.

Mahbub

read Stoer-Wagner algo + Karger-Stein algo here:
http://maagar.openu.ac.il/opus/Static/b ... s%5D_0.pdf
and here's a good step-by-step sample for stoer-wagner algo:
http://www.cs.dartmouth.edu/~rahul/Teac ... mincut.pdf

good luck.

Did anyone saved those pdfs? The links are down

at least one of the pdf's is still online: http://www.cs.dartmouth.edu/~ac/Teach/C ... mincut.pdf

do go to http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/, as it seems to have a few very interesting resources

nima101 wrote:hi everybody.
I've applied the Stoer-Wagner algo to find the min-edge-cut
but I'm getting WA!
I've tried any kind of test cases... (disconnected graph, containing bridge, complete graph, ....)
is there any tricky test data???
can any one give me some test data plz...
tnx in advance.

I also implement Stoer-Wagner algorithm and get AC. My program checks the input graph is a connected component or not. If it is not a connected component, output 0; otherwise, find min-cut by using Stoer-Wagner algorithm.