二分图最大匹配之匈牙利算法

二分图也是二部图，即可以将一个图分为两部分。

用男女举例，男生与女生有暧昧关系，同性之间是不存在暧昧的（同性才是真爱，异性只为传宗接代），则他们之间存在一条边，那么我们可以将男生，女生分开，男生在左边，女生在右边

我们可以发现在左边的男生是没有边相连的，右边的女生也是，他们只与对面的异性存在边，那么这就是一个二分图。

至于匹配问题也很好理解，这里可以看成夫妻关系，一个男生可以有几个暧昧的异性，但是只有一位妻子，女生也是如此；一对夫妻即一组匹配

那么在给出的一个二分图中，求最大匹配就是最多存在几对夫妻。

求二分图最大匹配这里介绍匈牙利算法：

强推这位博主讲的匈牙利：https://blog.csdn.net/dark_scope/article/details/8880547

给出一道洛谷的模板题：P3386 【模板】二分图匹配

这里给出我的代码：

 1 /*
 2 二分图最大匹配模板
 3 czq
 4 */
 5 
 6 #include <cstdio>
 7 #include <cstring>
 8 #include <iostream>
 9 using namespace std;
10 const int N = 1e3 + 10;
11 
12 int n, m, e;
13 int edges[N][N];
14 int vis[N], rec[N];
15 //rec记录配对情况
16 
17 inline bool match(int now)
18 {
19     for(int i = 1; i <= m; i++)
20     {
21         if(edges[now][i] == 1 && vis[i] == 0)
22         {
23             vis[i] = 1;
24             if(rec[i] == 0 || match(rec[i]))
25             {
26                 rec[i] = now;
27                 return true;
28             }
29         }
30     }
31     return false;
32 }
33 
34 int main()
35 {
36     memset(rec, 0, sizeof(rec));
37     memset(edges, 0, sizeof(edges));
38     cin >> n >> m >> e;
39     for(int i = 1; i <= e; i++)
40     {
41         int u, v;
42         cin >> u >> v;
43         edges[u][v] = 1;
44     }
45 
46     int ans = 0;
47 
48     for(int i = 1; i <= n; i++)
49     {
50         memset(vis, 0, sizeof(vis));
51         if(match(i))    ans++;
52     }
53 
54     cout << ans << endl;
55 
56     return 0;
57 }