Is there anybody use the perfect method to solve this
problem (not approximate method) ?

I'm better on memory - it was something like 66 kb .. it
runs on BC++ 3.1 for DOS.

I'm not better on time - i am two times slower then 0.03 ..
not sure, but slower. But i can speed it up probably! :))

It use about 50kb if I use Borland Pascal 7.0 :)
...I think we have equivalent solution.

Do you use algorithm which finds augmenting path
(alternating path, i'm not sure bout the terminology here)
and updates the flow?

This one is only for bipartite graphs, but runs on
these test cases.

> Do you use algorithm which finds augmenting path
> (alternating path, i'm not sure bout the terminology here)
> and updates the flow?
>
> This one is only for bipartite graphs, but runs on
> these test cases.
>

Nope, they're general graph all. But the algorithm is
still working, probably the test cases are random made,
and it's not failing to find the matching.

But Jivko Ganev is using general graph matching algorithm.

This is not supposed to be. I have created around 50 test
cases and have sent them to mb. In all of them the
bipartite algorithm fails. There is also a good amount of
them where Petko Minkov's randomized solution fails too. It
took my computer whole night to generate them, so as soon
they are uploaded I hope the greedy solutions will be
rejected.

Yes, I find augmenting path. It works not only on bipartite graphs. I can prove it. Send to me: chestiphar@mail.ru your mail. If I will have a time (now I have a session) I'll write you.

QH@