HDU：过山车（二分图最大匹配）

http://acm.hdu.edu.cn/showproblem.php?pid=2063

题意：有m个男，n个女，和 k 条边，求有多少对男女可以搭配。

思路：裸的二分图最大匹配，匈牙利算法。

枚举每一个男生，然后对其DFS，在DFS中枚举女生，如果有边相连的话，如果这个女生还没有搭档（match == -1），那么这个女生的搭档就是当前的男生，否则继续DFS这个女生的搭档，看看能不能让这个女生本来的搭档和其他女生搭配，从而给当前的男生腾出位置。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 #include <string>
 7 #include <iostream>
 8 #include <stack>
 9 #include <map>
10 #include <queue>
11 using namespace std;
12 #define N 1010
13 #define INF 0x3f3f3f3f
14 
15 int match[N];
16 int mp[N][N];
17 bool vis[N];
18 int n, m;
19 
20 bool dfs(int u)
21 {
22     for(int i = 1; i <= m; i++) {
23         if(mp[u][i] && !vis[i]) {
24             vis[i] = 1;
25             if(match[i] == -1 || dfs(match[i])) {
26                 match[i] = u;
27                 return true;
28             }
29         }
30     }
31     return false;
32 }
33 
34 int main()
35 {
36     int k;
37     while(scanf("%d", &k), k) {
38         scanf("%d%d", &m, &n);
39         memset(mp, 0, sizeof(mp));
40         for(int i = 1; i <= k; i++) {
41             int u, v;
42             scanf("%d%d", &u, &v);
43             mp[v][u] = 1;
44         }
45         int ans = 0;
46         memset(match, -1, sizeof(match));
47         for(int i = 1; i <= n; i++) {
48             memset(vis, 0, sizeof(vis));
49             if(dfs(i)) ans++;
50         }
51         printf("%d
", ans);
52     }
53     return 0;
54 }