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...

<verbatim> 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); </Verbatim>

-- Main.YuryKholondyrev - 17 Nov 2005