CodeArchive BPTShort

Bipartite Matching Short Version

This algorithm uses DFS to do the Hungarian Tree. It is fast, because it is just a 0-1 Maximum Flow problem, with maximum flow = n. It is short, because it uses DFS.

Latest version: uses adjacency matrix, more general...

int mmm(int now){
  for(int i = 0; i < asz[now]; i++)
    if(!vis[adj[now][i]] &&   (vis[adj[now][i]] = 1)  )
      if(match[adj[now][i]] == -1 || mmm(match[adj[now][i]]))
        { match[adj[now][i]] = now; match[now] = adj[now][i]; return 1; }
  return 0;
}

//memset(m, -1, sizeof(m));
//for(int i = 0; i < n; i++)
//  if(m[i] == -1) memset(vis, 0, sizeof(vis)), match(i);

-- Main.YuryKholondyrev - 17 Nov 2005