本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-09 14:11:54

二分图做法

我们考虑将每种试题拆成 $k$ 个点，作为左侧点，代表这种试题的可选项。

右侧点就是每个试题。每个试题与试题选项之间连边。

然后进行二分图匹配。我们知道，每个左侧点有唯一的匹配点，每个右侧点也最多匹配一个左侧点，于是符合题意。

网络流做法

我们设源点为 $S$，汇点为 $T$，那么 $S$ 与每个试题相连，容量均为一；$T$ 与每种类别相连，容量为其需要的数量。然后，试题与其所属于的类型相连，容量是一。

在这个网络中，如果最大流不为总共需要匹配的数量，那么就无解；否则直接找流量非零的点然后输出即可。

这样下来，一共需要 $n + k + 2$ 个点。

p.s. 感觉开始悟到二分图和网络流的一些用处了 /hsh