【网络流24题-洛谷P2763 试题库问题】

题目描述

«问题描述:

假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。

«编程任务:

对于给定的组卷要求,计算满足要求的组卷方案。

输入输出格式

输入格式:

第1行有2个正整数k和n (2 <=k<= 20, k<=n<= 1000)

k 表示题库中试题类型总数,n 表示题库中试题总数。第2 行有k 个正整数,第i 个正整数表示要选出的类型i的题数。这k个数相加就是要选出的总题数m。接下来的n行给出了题库中每个试题的类型信息。每行的第1 个正整数p表明该题可以属于p类,接着的p个数是该题所属的类型号。

输出格式:

第i 行输出 “i:”后接类型i的题号。如果有多个满足要求的方案,只要输出1个方案。如果问题无解,则输出“No Solution!”。

输入输出样例

输入样例#1:

输出样例#1:

说明

感谢 @PhoenixEclipse 提供spj

匹配问题,可用最大流来跑。本题题意有些模糊,根据答案应该是要题目不能重复选择,即就算一道题属于多类,最终选择也只能作为其中一类题选择。

那么,我们建立超级源点\(S\),超级汇点\(T\),由\(S\)向每个题目连一条容量为1的边;把每个种类都视作一个节点,并向超级汇点\(T\)连一条容量为该种类题所需数目的边;最后,每道题目向其所有的所属分类连一条容量为1的边,跑最大流即可。

若最大流=所需总题目数,则匹配方案就是题目与种类之间的满流边;否则无解。

代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*