Can't you tell me how to solve this problem?
I have used both Blossom and BFS but WA(19).

Blossom is O(N^4), BFS is wrong in fact - and I don't know absolutely correct and fast algo... So, my solution is just BFS-based heuristics.

Algorithm is not easy. I can send you a PDF.

Please send me. My email is quangviet2004@yahoo.com
Thanks

You can download it from
http://dl.by.ru/upload/p221-gabow.pdf

Edited by author 23.06.2004 03:14

To be fair with you I must admit that either the tests are easy or there's a much easier way to solve this problem. I used Berge's theorem (http://mathworld.wolfram.com/BergesTheorem.html) and I have AC (my C source is less than 1.5kB).

Gabow's algorithm also uses Berge's theorem. This theorem is basic in matching theory.

What method did you use?

My algorithm goes as follows:

do
  foundPath=false
  for i=1 to n do
  begin
    if exists augumenting path from vertex i then
    begin
      apply found path
      foundPath=true
    end
  end
while (foundPath)

Edited by author 23.06.2004 04:40

But how do you check if exists augumenting path?

I just use a DFS.

A simple DFS? Or something like random search?
Can you send me your source? See e-mail in my profile.

Can you send it to me? Thanks
quangviet2004@yahoo.com

I can send it to everyone who already has Accepted - otherwise it would be unfair.

But I can give you my DFS:

int FindAndApply(int v)
{
  visited[v] = 1;
  for (PEdge t=out[v]; t != NULL; t = t->next) {
    int u = t->v;
    if (u == S[v]) continue;
    if (visited[u] || visited[S[u]]) continue;
    visited[u] = 1;
    if (S[u] == 0 || FindAndApply(S[u])) {
      S[u] = v;
      S[v] = u;
      return 1;
    }
  }
  return 0;
}


S[i] holds a vertex matched with vertex i.

Edited by author 23.06.2004 19:33

You can send it to anybody now becouse it doesn't work anymore ;-) I've added several new tests. All wrong methods (BFS, DFS, random search) won't pass these tests.
If your wrong program still can get AC now, please tell me.