45-问题分析

7.7.1　问题分析

把题型看作X集合，试题库看作Y集合，就构成了一个二分图。Y集合中的题y_j属于哪些题型，则这些题型x_i与y_j之间有连线，连线的容量全部是1，保证该题型只能选择题y_j一次，如图7-149所示。

例如题库中试题y₁属于x₁、x₃两种题型，比如一道题既属于填空题又属于计算题。

该题属于二分图多重匹配问题。建立一个二分图，每个题型为X集合中的结点，每个试题为Y集合中的结点，增设源点s和汇点t。从源点s向每个题型x_i结点连接一条有向边，容量为该题型选出的数量c_i。从每个y_j结点向汇点t连接一条有向边，容量为1，以保证每道题只能被选中一次。Y集合中的题y_j属于哪些题型，则这些题型x_i与y_j之间有一条有向边，容量为1，如图7-150所示。