试题库问题
题目描述
问题描述：
假设一个试题库中有 (n) 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 (m) 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。
编程任务：
对于给定的组卷要求，计算满足要求的组卷方案。
输入格式
第一行有两个正整数 (k) 和 (n)。(k) 表示题库中试题类型总数，(n) 表示题库中试题总数。
第二行有 (k) 个正整数，第 (i) 个正整数表示要选出的类型 (i) 的题数。这 (k) 个数相加就是要选出的总题数 (m)。
接下来的 (n) 行给出了题库中每个试题的类型信息。每行的第一个正整数 (p) 表明该题可以属于 (p) 类，接着的 (p) 个数是该题所属的类型号。
输出格式
输出共 (k) 行，第 (i) 行输出 i: 后接类型 (i) 的题号。
如果有多个满足要求的方案，只要输出一个方案。
如果问题无解，则输出 No Solution!。
样例 #1
样例输入 #1
3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3
样例输出 #1
1: 1 6 8
2: 7 9 10
3: 2 3 4 5
提示
(2\leq k \leq 20)，(k \leq n \leq 10^3)。
思路
读完题，很明显的发现这是一个二分图
类型和题目是两个互不相交的集合，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集
很明显的二分图+最大流
从源点到每个类型建边，容量为每个类型所需要的题目数量
从每个类型向这个类型里面的题目建边，容量为 1
从每个题目到汇点建边，容量为 1
跑一遍dinic检验答案
代码实现
#include
#include
#include
#include
using namespace std;
int read()
{
int x=0,f=1;char c=getchar();
while (c'9'){if (c=='-')f=-1;c=getchar();}
while (c>='0'&&cn&&e[j]
Original: https://www.cnblogs.com/watasky/p/16467655.html
Author: watasky
Title: 【题解】试题库问题
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604136/
转载文章受原作者版权保护。转载请注明原作者出处！