Day66：HDU2063过山车二分图最大匹配模板题

题意：中文题，自己看吧

思路：二分图最大匹配模板题目

之前写的二分图是vector写的，https://www.cnblogs.com/OFSHK/p/12228048.html

所以这次上一个数组写的代码，

也算是一个模板

注意一下清空和输入格式

一定要注意清空啊，不然一直WAWAWA！！！！

AC代码：

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<queue>
 4 #include<string.h>
 5 using namespace std;
 6 #define inf 0x3f3f3f3f
 7 
 8 const int N=550;
 9 int k,woman,man;
10 int e[N][N],match[N];
11 bool book[N];
12 
13 int dfs(int x)
14 {
15     for(int i=1; i<=man; i++)
16     {
17         if(book[i]==0&&e[x][i])
18         {
19             book[i]=1;
20             if(match[i]==0||dfs(match[i]))
21             {
22                 match[i]=x;
23                 return 1;
24             }
25         }
26     }
27     return 0;
28 }
29 
30 int main()
31 {
32     //while(~scanf("%d %d %d",&k,&woman,&man))
33     while(~scanf("%d",&k)&&k)
34     {
35         scanf("%d %d",&woman,&man);
36         memset(e,0,sizeof(e));//注意清空，不然WA
37         memset(match,0,sizeof(match));//清空。。
38         for(int i=1; i<=k; i++)
39         {
40             int x,y;
41             scanf("%d %d",&x,&y);
42             e[x][y]=1;
43         }
44         int ans=0;
45         for(int i=1; i<=woman; i++)
46         {
47             memset(book,0,sizeof(book));//注意清空位置
48             if(dfs(i))
49                 ans++;
50         }
51         printf("%d\n",ans);
52     }
53     return 0;
54 }

View Code