«问题描述:
假设一个试题库中有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:
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
分析:
二分图多重匹配:超级源点0连向种类权值为所需题目数量,种类1~n连向其集合内的所有题数n+1~n+m,权值为1,每一道题目连向超级汇点n+m+1,权值为1。最终判断最大流是否等于源点的流出,然后根据残余网络路径权值,打印路径。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
typedef long long LL;
using namespace std;
const int MAXN = 2000 + 50;
const int INF = 0x3f3f3f3f;
int head[MAXN], dist[MAXN], vis[MAXN];
int cur[MAXN];
int n, m, val;
int top = 0;
struct Edge {
int to, cap, flow, next;
}edge[MAXN * 20];
void init() {
top = 0;
memset(head, -1, sizeof(head));
memset(vis, 0, sizeof(vis));
}
void addedge(int a, int b, int c) {
Edge E1 = {b, c, 0, head[a]};
edge[top] = E1;
head[a] = top++;
Edge E2 = {a, 0, 0, head[b]};
edge[top] = E2;
head[b] = top++;
}
bool BFS(int st, int ed) {
memset(dist, -1, sizeof(dist));
memset(vis, 0, sizeof(vis));
queue<int> que;
que.push(st);
vis[st] = 1;
dist[st] = 0;
while(!que.empty()) {
int u = que.front();
que.pop();
for(int i = head[u]; i != -1; i = edge[i].next) {
Edge E = edge[i];
if(!vis[E.to] && E.cap > E.flow) {
dist[E.to] = dist[u] + 1;
vis[E.to] = 1;
if(E.to == ed) return true;
que.push(E.to);
}
}
}
return false;
}
int DFS(int x, int a, int ed) {
if(x == ed || a == 0) return a;
int flow = 0, f;
for(int& i = cur[x]; i != -1; i = edge[i].next) {
Edge& E = edge[i];
if(dist[E.to] == dist[x] + 1 && (f = DFS(E.to, min(a, E.cap - E.flow), ed)) > 0) {
E.flow += f;
edge[i^1].flow -= f;
flow += f;
a -= f;
if(a == 0) break;
}
}
return flow;
}
int Maxflow(int st, int ed) {
int flow = 0;
while(BFS(st, ed)) {
memcpy(cur, head, sizeof(head));
flow += DFS(st, INF, ed);
}
return flow;
}
int main()
{
init();
int sum = 0;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; ++i) {
scanf("%d", &val);
sum += val;
addedge(0, i, val);
}
for(int i = 1; i <= m; ++i) {
addedge(i + n, n + m + 1, 1);
int k, op;
scanf("%d", &k);
for(int j = 1; j <= k; ++j) {
scanf("%d", &op);
addedge(op, i + n, 1);
}
}
int ans = Maxflow(0, n + m + 1);
if(ans != sum) {
puts("No Solution!");
return 0;
}
// printf("%d\n", ans);
for(int i = 1; i <= n; ++i) {
printf("%d:", i);
for(int j = head[i]; ~j; j = edge[j].next) {
if(edge[j].to > 0 && edge[j].flow > 0) {
printf(" %d", edge[j].to - n);
}
}
puts("");
}
return 0;
}