Difference between revisions of "CodeArchive BPTShort"
From Ubcacm
| Line 4: | Line 4: | ||
Latest version: uses adjacency matrix, more general... | Latest version: uses adjacency matrix, more general... | ||
| − | < | + | <pre> |
int mmm(int now){ | int mmm(int now){ | ||
for(int i = 0; i < asz[now]; i++) | for(int i = 0; i < asz[now]; i++) | ||
| Line 16: | Line 16: | ||
//for(int i = 0; i < n; i++) | //for(int i = 0; i < n; i++) | ||
// if(m[i] == -1) memset(vis, 0, sizeof(vis)), match(i); | // if(m[i] == -1) memset(vis, 0, sizeof(vis)), match(i); | ||
| − | </ | + | </pre> |
-- Main.YuryKholondyrev - 17 Nov 2005 | -- Main.YuryKholondyrev - 17 Nov 2005 | ||
Latest revision as of 19:05, 22 January 2007
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
