传送门：洛谷-试题库问题
题意
假设一个试题库中有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的有向边，并在该题与汇点之间也连一条容量为1的有向边。 接着跑最大流，一定要源点出发的每条边都流满了才有解。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<queue>
#define INF 0x7fffffff
using namespace std;
const int N=
2e6+
10;
int t[
22],head[N],to[N],nxt[N],w[N],flow[N];
int d[N],n,k,cnt,T=
2e5,dir[N],vis[
1002];
queue<int>Q;
inline int read()
{
char ch=getchar();
int x=
0,t=
1;
while(ch>
'9' || ch<
'0') {
if(ch==
'-') t=-
1;ch=getchar();}
while(ch>=
'0' && ch<=
'9') {x=(x<<
3)+(x<<
1)+(ch^
48);ch=getchar();}
return x*t;
}
inline void link(
int u,
int v,
int cap)
{
to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;w[cnt]=cap;
}
inline bool bfs()
{
memset(d,-
1,
sizeof(d));
d[
0]=
0;Q.push(
0);
while(!Q.empty()){
int now=Q.front();Q.pop();
for(
int i=head[now];i;i=nxt[i]){
if(d[to[i]]==-
1 && w[i]>flow[i]){
d[to[i]]=d[now]+
1;
Q.push(to[i]);
}
}
}
if(d[T]==-
1)
return false;
return true;
}
inline int min(
int x,
int y)
{
return x>y? y:x;
}
inline int dfs(
int st,
int ed,
int f)
{
if(st==ed)
return f;
int tot=
0;
for(
int i=head[st];i;i=nxt[i]){
if(d[to[i]]==d[st]+
1 && w[i]>flow[i]){
int ww=f-tot;
int qw=dfs(to[i],ed,min(w[i],ww));
if(qw>
0){
flow[i]+=qw;
flow[i^
1]-=qw;
tot+=qw;
if(tot==f)
return tot;
}
}
}
if(tot==
0) d[st]=-
1;
return tot;
}
inline void solve()
{
while(bfs()) dfs(
0,T,INF);
}
inline bool check()
{
for(
int i=head[
0];i;i=nxt[i]){
if(w[i]!=flow[i])
return false;
}
return true;
}
inline void print()
{
for(
int i=
1;i<=k;i++){
printf(
"%d: ",i);
for(
int j=head[i];j && t[i];j=nxt[j]){
if(!vis[to[j]]){
t[i]--;
vis[to[j]]=
1;
printf(
"%d ",to[j]-k);
}
}
printf(
"\n");
}
}
int main(){
k=read();n=read();
for(
int i=
1;i<=k;i++){
t[i]=read();link(
0,i,t[i]);link(i,
0,
0);
}
for(
int i=
1;i<=n;i++){
int op=read();
while(op--){
int in=read();
link(in,k+i,
1);link(k+i,in,
0);
link(k+i,T,
1);link(T,k+i,
0);
}
}
solve();
if(!check()){
printf(
"No Solution!\n");
return 0;
}
print();
return 0;
}
