面试排班问题
有\(n\)人前来参加面试，共有\(m\)场可供选择的面试。
- 第\(i\)个人从这些面试时间中，选出可参与的面试场次集合\(S_i\)。
- 第\(j\)场面试最多可容纳\(a_j\)人。
问是否存在方案，使得每个人都能参与面试。
例1 \(n=3, m = 4\)，
\[ S_1 = \{1, 2\}, \\ S_2 = \{1, 3,4\}, \\ S_3 = \{2\}, \\ a_m = \{ 1, 1, 1, 2 \} \]
存在方案\(\{(1, 1), (2, 4), (3, 2)\}\)或\(\{(1, 1), (2, 3), (3, 2)\}\)，使得每个人都能参与面试，其中数对\((i, j)\)表示安排第\(i\)个人参与第\(j\)场面试。
解答
暴力搜索，时间复杂度\(O(\prod |S_i|)\)。
正解：转换为无权二分图最大匹配问题：
14-2: 无权二部图中的最大匹配 Maximum-Cardinality Bipartite Matching (MCBM)_哔哩哔哩_bilibili
首先，为每人建立一个顶点，为左图。
记容纳\(a_j\)个人的面试场次为\(a_j\)个顶点，为所有面试场次建立\(\sum a_j\)个顶点，为右图。
若\(S_i\)包含\(j\)，则从左图顶点\(i\)引\(a_j\)条边，至第\(j\)场面试建立的顶点。
那么，问题转换为求该无权二分图的最大匹配。
本题不能使用匈牙利算法求解，因为左图和右图顶点数不同。
可归约到最大流问题后，用最大流算法求解。