试题库问题

题目描述

问题描述：

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

编程任务：

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

输入格式

第一行有两个正整数 kkk 和 nnn。kkk 表示题库中试题类型总数，nnn 表示题库中试题总数。

第二行有 kkk 个正整数，第 iii 个正整数表示要选出的类型 iii 的题数。这 kkk 个数相加就是要选出的总题数 mmm。

接下来的 nnn 行给出了题库中每个试题的类型信息。每行的第一个正整数 ppp 表明该题可以属于 ppp 类，接着的 ppp 个数是该题所属的类型号。

输出格式

输出共 kkk 行，第 iii 行输出 i: 后接类型 iii 的题号。
如果有多个满足要求的方案，只要输出一个方案。
如果问题无解，则输出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≤k≤202\leq k \leq 202≤k≤20，k≤n≤103k \leq n \leq 10^3k≤n≤103。

感谢 @PhoenixEclipse 提供 spj

1、 有n种题型（n <= 20）, 有m道题（m <= 1000） 
建图 ： 起点 0， 终点 n + m + 1.编号（1 ~ n） 表示题型;编号 (n + 1 ~ n + m) 表示题目;起点 0 与 （1 ~ n） 连上 n条边，边权就是这种题型需要匹配的题目(假设总数是sum);每种题型（1 ~ n）与之对应的题目，连边，边权是1;每道题（n + 1 ~ n + m）, 与终点（n + m + 1） 连边，边权是1另外， 所有的反边，边权都是0
2、 图建好了，就跑最大流EK算法。 当最大流 maxflow = sum， 说明有解。

#include 
using namespace std;
const int N = 1100, M = 23000;
int n, m;	//题型， 题目总数
int a[N];
int head[N], ver[M], edge[M], Next[M];
int incf[N], pre[N];
bool vis[N];
int s, t, tot, maxflow;
vector v[N];	// v[k] 表示题型k所选择的题目void add(int x, int y, int z)
{ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}bool bfs()
{memset(vis, false, sizeof vis);queue q;q.push(s); vis[s] = true;incf[s] = 0x3f3f3f3f;while(q.size()){int x = q.front(); q.pop();for(int i = head[x]; i; i = Next[i]){if(edge[i]){int y = ver[i];	if(vis[y])	continue;incf[y] = min(incf[x], edge[i]);pre[y] = i;q.push(y); vis[y] = true;if(y == t)return true;}}}return false;
}void update()
{int x = t;while(x != s){int i = pre[x];edge[i] -= incf[t];edge[i ^ 1] += incf[t];int y = ver[i ^ 1];if(1 <= y && y <= n){v[y].push_back(x - n);		// 记录没种题型对应的题目}x = y;}
}int main()
{scanf("%d%d", &n, &m);s = 0, t = n + m + 1;tot = 1;// n种题型， 点的编号 1 ~ n , 起点 s 与 这n个点连边int sum = 0;for(int i = 1; i <= n; ++i){scanf("%d", &a[i]);sum += a[i];add(0, i, a[i]); add(i, 0, 0);}int count, x;// m道题目，编号 n + 1 ~ n + m//  每道题 ---> 每种题型（编号 1 ~ m）//  题型 --> 题目  ， 连上一条边（边容量是1）for(int i = 1; i <= m; ++i){scanf("%d", &count);while(count--){scanf("%d", &x);	add(x, i + n, 1);add(i + n, x, 0);}}// 每道题 --> 终点（n + m + 1） 连上一条边（边容量是1）for(int i = 1; i <= m; ++i){add(n + i, n + m + 1, 1);add(n + m + 1, n + i, 0);}while(bfs()){update();}if(maxflow < 0)printf("No Solution!\n");else{for(int i = 1; i <= n; ++i){printf("%d:", i);int size = v[i].size();for(int j = 0; j < size; ++j){printf(" %d", v[i][j]);}printf("\n");}}return 0;
}