这道题目是经典的二分图最大匹配（Bipartite Matching） 问题。在信奥（OI）中，这是学习图论时必须掌握的基础模板题。
1. 题目分析
我们可以将题目中的信息抽象为一个二分图：
- 左侧集合：\(n\) 头奶牛。
- 右侧集合：\(m\) 个牛栏。
- 边：如果奶牛 \(i\) 喜欢牛栏 \(j\)，则在 \(i\) 和 \(j\) 之间连一条无向边。
题目要求“每个牛栏只能容纳一头奶牛，一头奶牛只能在一个牛栏中产奶”，这正是要求我们在这个二分图中找到最大匹配数（即选出尽可能多的边，使得任意两条边都没有公共端点）。
2. 核心算法：匈牙利算法 (Hungarian Algorithm)
解决二分图最大匹配最常用的算法是匈牙利算法。其核心思想是寻找增广路（Augmenting Path）。
算法步骤：
- 从第一头奶牛开始，尝试给它安排一个它喜欢的牛栏。
- 如果该牛栏还没人（未匹配），直接分配给它。
- 如果该牛栏已经被奶牛 \(B\) 占用了，我们就去问奶牛 \(B\)：“你能不能换一个你喜欢的其他牛栏？”
- 如果奶牛 \(B\) 能换到另一个空的或能腾出来的牛栏，那么当前的奶牛就可以拥有这个牛栏。
- 如果奶牛 \(B\) 实在挪不动，当前奶牛就尝试下一个它喜欢的牛栏。
- 重复以上过程，直到所有奶牛都尝试过。
3. C++ 代码实现
这里使用邻接表来存储奶牛的喜好，match 数组记录牛栏当前所属的奶牛。
#include <iostream>
#include <vector>
#include <cstring>using namespace std;const int MAXN = 205; // 奶牛和牛栏的最大数量vector<int> adj[MAXN]; // 邻接表：adj[i] 存储奶牛 i 喜欢的牛栏编号
int match[MAXN]; // match[j] 表示牛栏 j 当前匹配的奶牛编号
bool vis[MAXN]; // vis[j] 在单次 DFS 中记录牛栏 j 是否已被访问过int n, m;// 匈牙利算法的核心：寻找增广路
bool dfs(int u) {for (int v : adj[u]) { // 遍历奶牛 u 喜欢的每一个牛栏 vif (!vis[v]) {vis[v] = true; // 标记牛栏 v 在这一轮匹配中已被考虑// 如果牛栏 v 没有匹配，或者原先匹配牛栏 v 的奶牛可以去找别的牛栏if (match[v] == 0 || dfs(match[v])) {match[v] = u; // 匹配成功，更新牛栏 v 的归属return true;}}}return false;
}int main() {// 快速输入输出优化ios::sync_with_stdio(false);cin.tie(0);if (!(cin >> n >> m)) return 0;for (int i = 1; i <= n; ++i) {int s, stall;cin >> s;while (s--) {cin >> stall;adj[i].push_back(stall);}}int max_matches = 0;for (int i = 1; i <= n; ++i) {memset(vis, false, sizeof(vis)); // 每一头奶牛匹配前，清空访问标记if (dfs(i)) {max_matches++;}}cout << max_matches << endl;return 0;
}
4. 关键点解析
vis数组的作用：在一次dfs(i)的递归过程中，vis确保我们不会陷入死循环（比如奶牛 A 抢奶牛 B 的位子，奶牛 B 又想抢回 A 原有的位子）。每一轮为新奶牛寻找匹配时，vis都要重置。- 时间复杂度：\(O(N \cdot E)\)，其中 \(N\) 是奶牛数量，\(E\) 是总的喜好边数。对于 \(N, M \le 200\) 的规模，这个算法运行得非常快。
- 空间复杂度：\(O(N + M + E)\)。
5. 教学建议
在给学生讲解时，可以把这个过程比作“霸占座位的连锁反应”。
- 新同学想坐某个位置。
- 位置上有人，就请那个人挪走。
- 那个人挪走的前提是，他也能找到（或抢到）新位置。
- 如果一连串的挪动都能成功，那么总人数（匹配数）就加 1。