poj1274 The Perfect Stall

题意：
二分图最大匹配。
思路：
匈牙利算法。
实现：
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <vector>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int MAXN = 500;
 8 vector<int> G[MAXN + 5];
 9 int n, m, k;
10 bool used[MAXN + 5];
11 int match[MAXN + 5];
12 
13 bool dfs(int v)
14 {
15     used[v] = true;
16     for (int i = 0; i < G[v].size(); i++)
17     {
18         int u = G[v][i];
19         int w = match[u];
20         if (w == -1 || !used[w] && dfs(w))
21         {
22             match[v] = u;
23             match[u] = v;
24             return true;
25         }
26     }
27     return false;
28 }
29 
30 int max_match()
31 {
32     int res = 0;
33     for (int i = 1; i <= n + m; i++)
34     {
35         if (match[i] == -1)
36         {
37             memset(used, 0, sizeof(used));
38             if (dfs(i))
39                 res++;
40         }
41     }
42     return res;
43 }
44 
45 int main()
46 {
47     while (cin >> n >> m)
48     {
49         for (int i = 1; i <= n + m; i++)
50         {
51             G[i].clear();
52         }
53         memset(match, -1, sizeof(match));
54         for (int i = 1; i <= n; i++)
55         {
56             int tmp;
57             scanf("%d", &k);
58             while (k--)
59             {
60                 scanf("%d", &tmp);
61                 G[i].push_back(tmp + n);
62                 G[tmp + n].push_back(i);
63             }
64         }
65         cout << max_match() << endl;
66     }
67     return 0;
68 }
总结：
还可以使用最大流算法。