poj 2239 Selecting Courses

二分图基础。
求二分图最大匹配（匈牙利算法）。
View Code
 1 /*
 2 Author:Zhaofa Fang
 3 Lang:C++
 4 */
 5 #include <cstdio>
 6 #include <cstdlib>
 7 #include <iostream>
 8 #include <cmath>
 9 #include <cstring>
10 #include <algorithm>
11 #include <string>
12 #include <vector>
13 #include <queue>
14 #include <stack>
15 #include <map>
16 #include <set>
17 #define pb push_back
18 using namespace std;
19 
20 //==========================================
21 //二分图最大匹配
22 
23 const int maxn=305;
24 bool maz[maxn][maxn],vist[maxn];
25 int match[maxn],n,m;
26 
27 bool dfs(int u)
28 {
29     for(int v=1;v<=m;v++)
30     {
31         if(maz[u][v] && !vist[v])
32         {
33             vist[v]=true;
34             if(match[v] == -1 || dfs(match[v]))
35             {
36                 match[v]=u;
37                 return true;
38             }
39         }
40     }
41     return false;
42 }
43 
44 int Match()
45 {
46     int cnt=0;
47     memset(match,-1,sizeof(match));
48     for(int u=1;u<=n;u++)
49     {
50         memset(vist,false,sizeof(vist));
51         if(dfs(u))cnt++;
52     }
53     return cnt;
54 }
55 
56 int main()
57 {
58     while(~scanf("%d",&n))
59     {
60         memset(maz,0,sizeof(maz));
61         m=0;
62         for(int i=1;i<=n;i++)
63         {
64             int t;
65             scanf("%d",&t);
66             while(t--)
67             {
68                 int q,p;
69                 scanf("%d%d",&q,&p);
70                 maz[i][q*12+p]=true;
71                 m=max(m,q*12+p);
72             }
73         }
74         printf("%d\n",Match());
75     }
76     return 0;
77 }