二分图匹配模板（dfs+bfs）

dfs版：

[cpp] view plain copy print?

1. bool dfs(int u)  
2. {  
3.     for(int i = head[u]; ~i; i = e[i].next) {  
4.         int v = e[i].v;  
5.         if(!vis[v]) {  
6.             vis[v] = true;  
7.             if(my[v] == -1 || dfs(my[v])) {  
8.                 my[v] = u;  
9.                 mx[u] = v;  
10.                 return true;   
11.             }  
12.         }  
13.     }  
14.     return false;  
15. }  
16.   
17. int hungary()  
18. {  
19.     int ret = 0;  
20.     memset(mx, -1, sizeof(mx));  
21.     memset(my, -1, sizeof(my));  
22.     for(int i = 1; i <= X; i++) {  
23.         if(mx[i] == -1) {  
24.             memset(vis, 0, sizeof(vis));  
25.             if(dfs(i)) ret++;  
26.         }  
27.     }  
28.     return ret;  
29. }  

bfs版：

[cpp] view plain copy print?

1. 1. bool bfs(int st)  
   2. {  
   3.     queue <int> q;  
   4.     q.push(st);  
   5.     pre[st] = -1;  
   6.     bool flag = false;  
   7.     while(!q.empty() && !flag) {  
   8.         int u = q.front(); q.pop();  
   9.         for(int i = head[u]; ~i && !flag; i = e[i].next) {  
   10.             int v = e[i].v;  
   11.             if(vis[v] != st) {  
   12.                 vis[v] = st;  
   13.                 q.push(my[v]);  
   14.                 if(~my[v]) pre[my[v]] = u;  
   15.                 else {  
   16.                     int a = u, b = v;  
   17.                     flag = true;  
   18.                     while(~a) {  
   19.                         int t = mx[a];  
   20.      ���겻��,���겻��                   mx[a] = b;  
   21.                         my[b] = a;  
   22.                         a = pre[a];  
   23.                         b = t;  
   24.                     }  
   25.                 }  
   26.             }  
   27.         }  
   28.     }  
   29.     return mx[st] != -1;  
   30. }  
   31.   
   32. int hungary()  
   33. {  
   34.     int ret = 0;  
   35.     memset(mx, -1, sizeof(mx));  
   36.     memset(my, -1, sizeof(my));  
   37.     memset(vis, -1, sizeof(vis));  
   38.     for(int i = 1; i <= nX; i++) {//number from 1  
   39.         if(mx[i] == -1) {  
   40.             if(bfs(i)) ret++;  
   41.         }  
   42.     }  
   43.     return ret;  
   44. }