面试排班问题

\(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\)场面试建立的顶点。

那么,问题转换为求该无权二分图的最大匹配。

本题不能使用匈牙利算法求解,因为左图和右图顶点数不同。

可归约到最大流问题后,用最大流算法求解。