题目分析

我们有：

• $n$ 个飞行员，编号 $1$ 到 $n$
• 前 $m$ 个是正驾驶员（$1 \dots m$）
• 后 $n-m$ 个是副驾驶员（$m+1 \dots n$）
• 给定若干 $(a,b)$ 表示正驾驶员 $a$ 可以和副驾驶员 $b$ 搭档
• 每架飞机需要 1个正驾驶 + 1个副驾驶，且每人只能在一架飞机上

目标：最多能组成多少架飞机。

建模

我们可以将问题抽象为：

• 左部 $L$：正驾驶员集合 $\{1,2,\dots,m\}$
• 右部 $R$：副驾驶员集合 $\{m+1, m+2, \dots, n\}$
• 边：给定的可搭配关系 $(a,b)$

这就是在二分图中找最大匹配。

算法选择

由于 $n \leq 100$，我们可以用：

1. 匈牙利算法（DFS增广）
   • 时间复杂度 $O(n \times e)$，足够快
2. 网络流最大流
   • 建立超级源点连所有正驾驶员，所有副驾驶员连超级汇点，可搭配的连边，容量为1
   • 跑最大流即可

这里我们用匈牙利算法实现更简单。

匈牙利算法步骤

1. 建立邻接表 g[i] 表示左部点 $i$ 能匹配的右部点列表
2. 维护 match[j] 表示右部点 $j$ 当前匹配的左部点（0表示未匹配）
3. 对每个左部点 $u$，执行 DFS 寻找增广路：
   • 遍历 $u$ 的所有邻接右部点 $v$
   • 如果 $v$ 未在当前 DFS 访问过，则标记访问
   • 如果 $v$ 未匹配，或者 match[v] 可以找到新的匹配，则让 $u$ 匹配 $v$
4. 统计成功匹配的数量

样例验证

输入：

10 5
1 7
2 6
2 10
3 7
4 8
5 9

构建的二分图：

• 1 → 7
• 2 → 6, 10
• 3 → 7
• 4 → 8
• 5 → 9

匹配过程（一种可能）：

1. 1 匹配 7
2. 2 匹配 6
3. 3 无法匹配 7（7已被1占），但1可以换到无冲突？这里3无法抢到7，因为1没有其他选择
4. 4 匹配 8
5. 5 匹配 9

最终匹配：{(1,7), (2,6), (4,8), (5,9)}，共4对，输出4。

复杂度分析

• 每个左部点一次DFS，最多访问所有边
• 时间复杂度：$O(m \times (n+m))$，在 $n \leq 100$ 时非常快

这就是该问题的完整解法。