问题分析

我们有：

• $k$ 种试题类型（类别）
• $n$ 道试题，每道题可能属于多个类别
• 需要抽取 $m$ 道题组成试卷，其中类型 $i$ 需要 $r_i$ 道题（$\sum r_i = m$）
• 每道题只能被选用一次

目标：找出一个满足类型要求的选题方案，或判断无解。

建模思路

这是一个二分图多重匹配问题：

• 左部：$n$ 道试题（编号 $1 \dots n$）
• 右部：$k$ 种类型（编号 $1 \dots k$）

匹配规则：

1. 每道题只能匹配到一个类型（因为一道题在试卷中只能出现一次）
2. 每个类型 $i$ 需要匹配恰好 $r_i$ 道题
3. 只有试题 $j$ 属于类型 $i$ 时，才能进行匹配

网络流建图

建立网络流模型：

1. 源点 $S$ 向每道试题 $i$ 连一条容量为 $1$ 的边
   → 保证每道题最多被选用一次

2. 试题 $i$ 向它所属的所有类型 $j$ 连一条容量为 $1$ 的边
   → 保证试题只能分配到其实际所属的类型

3. 每个类型 $j$ 向汇点 $T$ 连一条容量为 $r_j$ 的边
   → 保证类型 $j$ 恰好选出 $r_j$ 道题

可行性判定

计算从 $S$ 到 $T$ 的最大流：

• 如果最大流值等于 $m$（总需求题数），则问题有解
• 否则无解，输出 No Solution!

方案输出

从网络流的流量分配中还原方案：

对于每个类型 $j$，检查所有从试题 $i$ 到类型 $j$ 的边：

• 如果这条边上的流量为 $1$（即满流），说明试题 $i$ 被分配到了类型 $j$
• 收集所有这样的试题 $i$，就是该类型选中的题目

样例分析

输入：

3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3

• $k=3$ 种类型，$n=15$ 道题
• 类型需求：类型1要3题，类型2要3题，类型3要4题，总计 $m=10$ 题
• 如第1题属于类型1和2，第2题只属于类型3

建图后求得最大流为10，等于总需求，有解。

输出方案：

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

验证：

• 类型1：3道题（1,6,8）
• 类型2：3道题（7,9,10）
• 类型3：4道题（2,3,4,5）
• 所有题目不重复，且都实际属于对应类型

算法复杂度

• 节点数：$n + k + 2$
• 边数：$O(n + n \times k)$
• 使用 Dinic 算法：$O(V^2 E) = O((n+k)^2 \cdot nk)$
• 在 $k \leq 20, n \leq 1000$ 时完全可行

总结

这道题通过将试题和类型建模为二分图的两部，用容量为1的边保证每道题只用一次，用类型到汇点的容量限制保证各类型的题目数量，将组卷问题转化为网络流最大流问题，能够高效地求解或判断无解。