试题库问题

· · 个人记录

二分图做法

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

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

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

网络流做法

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

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

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

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