题目：
假设一个试题库中有n道试题。 每道试题都标明了所属类别。同一道题可能有多个类别
属性。现要从题库中抽取 m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个
满足要求的组卷算法。
由文件input.txt提供输入数据。 文件第1行有2个正整数n和k (2 <=k<= 20, k<=n<= 1000)
k 表示题库中试题类型总数，n 表示题库中试题总数。第 2 行有 k 个正整数，第 i 个正整数
表示要选出的类型i的题数。这k个数相加就是要选出的总题数m。接下来的n行给出了题
库中每个试题的类型信息。每行的第1 个正整数 p表明该题可以属于 p类，接着的 p个数是
该题所属的类型号。
分析：
明显的网络流模型，对于每个试题，连一条边(S,i,1)
对于每个试题类型，连一条边(i,T,tmp)。其中tmp表示这个类型需要多少题。
然后最大流。
如果流量等于SUM(tmp)，有解，按要求输出，否则，输出No Solution！
HINT
我写的check程序(No Solution 请手测)：
#include
int n,m,a[2000][2000],num[2000],v[2000];
void init(){
cin >> m >> n;
for (int i=1;i<=m;i++) scanf("%d",&num[i]);
for (int i=1;i<=n;i++){
int num,tmp;
scanf("%d",&num);
for (int j=1;j<=num;j++){
scanf("%d",&tmp);
a[i][tmp]=1;
}
}
}
bool work(){
for (int i=1;i<=m;i++){
int tmp;
scanf("%d:",&tmp);
if (tmp!=i) return false;
for (int j=1;j<=num[i];j++){
scanf("%d",&tmp);
if (v[tmp]==1) return false;
if (a[tmp][i]==0) return false;
v[tmp]=1;
}
}
return true;
}
int main(){
freopen("input.txt","r",stdin);
init();
freopen("output.txt","r",stdin);
freopen("result.txt","w",stdout);
if (work()) cout << "AC" << endl;
else cout << "WA" << endl;
}
code：
#include
const int P=10000;
const int E=2000000;
const int INF=0x7FFFFFFF;
struct gtp{int x,y,next,c,op;}g[E];
int n,m,e=0,ls[P],fa[P],cur[P],d[P],num[P],total=0;
int link[1000][1000];
inline void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=e; g[e].c=c; g[e].op=e+1;
e++;
g[e].x=y; g[e].y=x; g[e].next=ls[y]; ls[y]=e; g[e].c=0; g[e].op=e-1;
}
void init(){
scanf("%d%d",&m,&n);
for (int i=1;i<=n;i++) addedge(0,i,1);
for (int i=1;i<=m;i++){
int tmp;
scanf("%d",&tmp);
addedge(n+i,m+n+1,tmp);
total+=tmp;
}
for (int i=1;i<=n;i++){
int num,tmp;
scanf("%d",&num);
for (int j=1;j<=num;j++){
scanf("%d",&tmp);
addedge(i,tmp+n,1);
}
}
}
void relabel(int k){
int min=m+n+1;
cur[k]=ls[k];
for (int i=ls[k];i!=0;i=g[i].next)
if (g[i].c>0 && d[g[i].y]
d[k]=min+1;
}
void change(int &flow){
int nf=INF;
for (int i=n+m+1;i!=0;i=g[fa[i]].x)
if (g[fa[i]].c
for (int i=n+m+1;i!=0;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
}
int sap(){
int flow=0;
for (int i=0;i<=n+m+1;i++){
d[i]=0;
cur[i]=ls[i];
num[i]=0;
}
num[0]=n+m+2;
int i=0;
while (d[0]
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
cur[i]=g[cur[i]].next;
}
if (cur[i]==0){
num[d[i]]–;
if (num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=0) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==n+m+1){
change(flow);
i=0;
}
}
}
return flow;
}
void work(){
int flow=sap();
if (flow
for (int i=1;i<=e;i++)
if (i%2==1 && g[i].c==0 && 1<=g[i].x && g[i].x<=n && n+1<=g[i].y && g[i].y<=n+m){
link[g[i].y-n][0]++;
link[g[i].y-n][link[g[i].y-n][0]]=g[i].x;
}
for (int i=1;i<=m;i++){
cout << i << ":";
for (int j=1;j<=link[i][0];j++)
cout << link[i][j] << " ";
cout << endl;
}
}
}
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
init();
work();
}