题目描述

问题描述:

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

洛谷P2763 试题库问题

?编程任务:

对于给定的组卷要求,计算满足要求的组卷方案。
输入输出格式

输入格式:

第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 ,将题目类型连接到S,流量设为需求,

然后将题目编号连接到T,流量设为1,

题目属于哪种类型的,就从这种类型向该题目连一条流量为1的边,

就建好了。

跑最大流,如果最大流和总需求题目数一样的话,说明有方案;

如果不一样的话就 “No Solution!”

输出方案的话…

题目类型连向题目编号,的边的剩余流量为0的表示匹配上了,

所以按照这种性质输出方案。

 

分类: 图论题解

说点什么

avatar
  Subscribe  
提醒