46-算法设计

7.7.2　算法设计

这是一个二分图多重匹配问题，用最大流解决。

（1）构建网络

根据输入的数据，建立二分图，每个题型为X集合中的结点，每个试题为Y集合中的结点，增设源点s和汇点t。从源点s向每个题型x_i结点连接一条有向边，容量为该题型选出的数量c_i。从每个y_j结点向汇点t连接一条有向边，容量为1，以保证每道题只能选中一次。Y集合中的题y_j属于哪些题型，则这些题型x_i与y_j之间有一条有向边，容量为1，创建混合网络。

（2）求网络最大流

（3）输出抽取方案

如果最大流值等于源点s与X集合所有结点边容量之和，则说明试题抽取成功，否则无解。对于每个题型，从X集合对应题型结点出发，所有流量为1的边指向的Y集合的结点就是该题型选中的试题号。即x_i结点的在Y集合的所有流量为1的邻接结点就是该题型选中的试题号。