【模板】二分图匹配

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 
 6 int n, m, k, cp, cnt;
 7 int girl[1010], to[1000001], next[1000001], head[1010];
 8 //girl[i]记录第i个girl所属的boy 
 9 bool dog[1010];
10 //dog[i]记录girl_i是否脱单 
11 
12 inline void add(int x, int y)
13 {
14     to[cnt] = y;
15     next[cnt] = head[x];
16     head[x] = cnt++;
17 }
18 
19 int find_girl(int u)
20 {
21     int i, v;
22     for(i = head[u]; i != -1; i = next[i])//找所有有好感的对象 
23     {
24         v = to[i];
25         if(!dog[v])//单身妹子
26         {
27             dog[v] = 1;
28             if(!girl[v] || find_girl(girl[v]))//名花无主或者能腾出个位置来
29             {
30                 girl[v] = u;
31                 return 1;
32             }
33         }
34     }
35     return 0;
36 }
37 
38 int main()
39 {
40     int i, j, x, y;
41     scanf("%d %d %d", &n, &m, &k);
42     memset(head, -1, sizeof(head));
43     for(i = 1; i <= k; i++)
44     {
45         scanf("%d %d", &x, &y);
46         add(x, y);//有暧昧关系 
47     }
48     for(i = 1; i <= n; i++)
49     {
50         memset(dog, 0, sizeof(dog));
51         if(find_girl(i)) cp++;
52     }
53     printf("%d", cp);
54     return 0;
55 }