题目描述
«问题描述：
假设一个试题库中有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
思路：网络流最大流，建立超级源点，向各种类型的题目连边，权值为各类型题目数量，各类型题目再向所对应的题目连边，权值为1，因为只有一道，最后连向汇点。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include<bits/stdc++.h> #define REP(i, a, b) for(int i = (a); i <= (b); ++ i) #define REP(j, a, b) for(int j = (a); j <= (b); ++ j) #define PER(i, a, b) for(int i = (a); i >= (b); -- i) using namespace std; template <class T> inline void rd(T &ret){ char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9'){ ret = ret * 10 + (c - '0'), c = getchar(); } } const int maxn=1e5+5; struct node{int v,val,nx;}p[maxn]; int k,n,s,t,tot,m,tmp,cur,ans,depth[maxn],head[maxn]; void add(int u,int v,int w){ p[++tot].val=w,p[tot].v=v,p[tot].nx=head[u],head[u]=tot; } queue<int>q; int bfs(){ q.push(s); memset(depth,0,sizeof(depth)); depth[s]=1; while(q.size()){ int now=q.front(); q.pop(); for(int i=head[now];i;i=p[i].nx){ int v=p[i].v; if(!depth[v]&&p[i].val>0){ depth[v]=depth[now]+1; q.push(v); } } } return depth[t]; } int dfs(int u,int c){ if(u==t||!c)return c; int qe=0; for(int i=head[u];i;i=p[i].nx){ int to=p[i].v; if(depth[to]==depth[u]+1&&p[i].val>0){ int ac=dfs(to,min(c,p[i].val)); if(ac>0){ p[i].val-=ac,p[i^1].val+=ac; c-=ac,qe+=ac; if(!c)return qe; } } } return qe; } int dinic(){ while(bfs())ans+=dfs(s,0x3f3f3f3f); return ans; } int main(){ rd(k),rd(n),t=k+n+1; for(int i=1;i<=k;i++){ rd(tmp),m+=tmp,add(s,i,tmp),add(i,s,0); } for(int i=1;i<=n;i++){ rd(cur); for(int j=1;j<=cur;j++){ rd(tmp),add(tmp,i+k,1),add(i+k,tmp,0); } } for(int i=1;i<=n;i++)add(i+k,t,1),add(t,i+k,0); if(dinic()==m){ for(int i=1;i<=k;i++){ cout<<i<<": "; for(int j=head[i];j;j=p[j].nx){ if(p[j].v>0&&!p[j].val){ cout<<p[j].v-k<<' '; } } cout<<endl; } } else cout<<"No Solution!"<<endl; return 0; }