匈牙利算法模板 hdu 1150 Machine Schedule（二分匹配）

二分图：https://blog.csdn.net/c20180630/article/details/70175814

https://blog.csdn.net/flynn_curry/article/details/52966283

匈牙利算法模板：https://blog.csdn.net/sunny_hun/article/details/80627351

例题：hdu 1150 Machine Schedule

参考：https://www.cnblogs.com/qq-star/p/4675600.html

https://www.cnblogs.com/kuangbin/archive/2012/08/19/2646928.html

注意：要用scanf输入输出！

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int N=105;
 6 int line[N][N],used[N],girl[N];
 7 int n,m;//n相当于左点书，m右点数
 8 bool find(int x)//模板
 9 {
10     int j;
11     for (j=1;j<m;j++)
12     {
13         if (line[x][j]==true && used[j]==false)
14         {
15             used[j]=1;
16             if (girl[j]==0 || find(girl[j]))
17             {
18                 girl[j]=x;
19                 return true;
20             }
21         }
22     }
23     return false;
24 }
25 int main()
26 {
27     int k;
28     while (cin>>n)
29     {
30         if (!n)
31         {
32             break;
33         }
34         cin>>m>>k;
35         memset(line,0,sizeof(line));
36         memset(girl,0,sizeof(girl));
37         while (k--)
38         {
39             int ind,a,b;
40             cin>>ind>>a>>b;
41             line[a][b]=1;
42         }
43         int ans=0;
44         for (int i=1;i<n;i++)//因为初始状态为0，所以不用考虑0状态
45         {
46             memset(used,0,sizeof(used));
47             if (find(i))
48             {
49                 ans++;
50             }
51         }
52         cout<<ans<<endl;
53     }
54 
55     return 0;
56 }