POJ1274（匈牙利算法）

题目，参考：https://blog.csdn.net/Runner__1/article/details/49928089
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 const int N=205;
 6 int pre[N],used[N];//pre存匹配，used为临时改动标记
 7 int ma[N][N];//存二分图
 8 int n,m,ans;//n为牛数，m为谷仓数
 9 int findit(int x)//匈牙利算法
10 {
11     int j;
12     for (j=1;j<=m;j++)
13     {
14         if (ma[x][j]!=0&&used[j]==0)//尝试匹配
15         {
16             used[j]=1;
17             if (pre[j]==0||findit(pre[j]))//如果未匹配或能调整出空位
18             {
19                 pre[j]=x;//匹配
20                 return 1;
21             }
22         }
23     }
24     return 0;
25 }
26 int main()
27 {
28 //    freopen("in.txt","r",stdin);
29     while (scanf("%d%d",&n,&m)!=EOF)
30     {
31         memset(ma,0,sizeof(ma));
32         for (int i=1;i<=n;i++)//输入
33         {
34             int temp;
35             scanf("%d",&temp);
36             for (int j=1;j<=temp;j++)
37             {
38                 int tt;
39                 scanf("%d",&tt);
40                 ma[i][tt]=1;
41             }
42         }
43         memset(pre,0,sizeof(pre));
44         ans=0;
45         for (int i=1;i<=n;i++)//注意是<=n!
46         {
47             memset(used,0,sizeof(used));
48             if (findit(i))
49             {
50                 ans++;
51             }
52         }
53         printf("%d
",ans);
54     }
55 
56     return 0;
57 }