二分图匹配模板

 1 #include <iostream>
 2 #include<bits/stdc++.h>
 3 //二分图匹配，在find函数理解。
 4 //找增广路，增广路的定义是从为匹配的节点出发，终止与未匹配的节点，中间是交替路。
 5 //find函数的递归不是一层一层的，而是直接dfs一个节点的匹配的节点
 6 //然后沿着增广路修改相互匹配的节点，在寻找过程中，用vis标记节点是否在增广路中，可以保证找的路线就是交替路，
 7 #include <iostream>
 8 using namespace std;
 9 const int N = 505;
10 vector<int>ve[2 * N];
11 bool vis[2 * N];
12 int match[2 * N];
13 int k, m, n;
14 bool find(int u) {
15     for (int i = 0; i < ve[u].size(); i++) {
16         int v = ve[u][i];
17         if (!vis[v]) {//不在交替路中
18             vis[v] = true;//放入交替路中
19             if (match[v] == -1 || find(match[v])) {
20                 //最后找到未匹配的点，说明找到一条增广路。
21                 //交换路径，返回成功。
22                 match[v] = u;
23                 match[u] = v;
24                 return true;
25             }
26         }
27     }
28     return false;
29 }
30 void count() {
31     int ans = 0;
32     for (int i = 1; i <=m + n; i++) {
33         if (match[i] == -1) {
34             memset(vis, false, sizeof(vis));
35             if (find(i))ans++;
36         }
37     }
38     cout << ans << endl;
39 }
40 void init() {
41     for (int i = 0; i < 2 * N; i++) {
42         ve[i].clear();
43     }
44     memset(match, -1, sizeof(match));
45 }
46 int main()
47 {
48 
49     int u, v;
50     while (scanf("%d", &k) && k) {
51         scanf("%d%d", &m, &n);
52         init();
53         for (int i = 0; i < k; i++) {
54             scanf("%d%d", &u, &v);
55             ve[u].push_back(v + m);
56             ve[v + m].push_back(u);
57         }
58         count();
59     }
60 
61     return 0;
62 }

bool bfs()
{
    queue<int> q;
    bool tag[N];
    //memset(tag,false,sizeof(tag));
    memset(vis,false,sizeof(vis));
    for (int j=1;j<=n;j++) if (!vis[j]) { // 遇到没染色的点就从它出发去染色其它点
        q.push(j);
        tag[j]= vis[j]=true;
        while(!q.empty()){
            int t=q.front();  q.pop();
            for (int i=1;i<=n;i++) if (g[t][i] && i!=t)
            {
                if (vis[i]){
                    if (tag[i]==tag[t]) return false;
                } else{
                   tag[i]=!tag[t];
                   q.push(i);
                   vis[i]=true;
                }
            }
        }
    }

    return true;
}