Cogs 732. [网络流24题] 试题库(二分图)

[网络流24题] 试题库 ★★ 输入文件：testlib.in 输出文件：testlib.out 评测插件 时间限制：1 s 内存限制：128 MB «问题描述： 假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 «编程任务： 对于给定的组卷要求，计算满足要求的组卷方案。 «数据输入： 由文件testlib.in提供输入数据。文件第1行有2个正整数k和n (2 <=k<= 20, k<=n<= 1000)k 表示题库中试题类型总数，n 表示题库中试题总数。第2 行有k 个正整数，第i 个正整数表示要选出的类型i 的题数。这k个数相加就是要选出的总题数m。接下来的n行给出了题库中每个试题的类型信息。每行的第1 个正整数p表明该题可以属于p类，接着的p个数是该题所属的类型号。 «结果输出: 程序运行结束时，将组卷方案输出到文件testlib.out 中。文件第i 行输出 “i：”后接类型i的题号。如果有多个满足要求的方案，只要输出1 个方案。如果问题无解，则输出“NoSolution!”。 输入文件示例 testlib.in 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 输出文件示例 testlib.out 1: 1 6 8 2: 7 9 10 3: 2 3 4 5 /* 建图挺简单的 跑二分图最大匹配. 主要是print. 也挺简单的 搞搞流量就好了.. 反正这题挺简单的... */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define MAXN 2001 #define INF 1e9 using namespace std; int n,k,S,T,ans,sum,cut=1,tot,tmp[MAXN],dis[MAXN],head[MAXN],c[MAXN],p[MAXN]; queue<int>q; bool b[MAXN]; struct data{int u,v,next,c;}e[MAXN*6]; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return x*f; } void add(int u,int v,int c) { e[++cut].u=u;e[cut].v=v;e[cut].c=c;e[cut].next=head[u];head[u]=cut; e[++cut].u=v;e[cut].v=u;e[cut].c=0;e[cut].next=head[v];head[v]=cut; } bool bfs() { for(int i=S;i<=T;i++) dis[i]=-1;dis[S]=0; q.push(S); while(!q.empty()) { int u=q.front();q.pop();b[u]=0; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(dis[v]==-1&&e[i].c) { dis[v]=dis[u]+1; q.push(v); } } } return dis[T]!=-1; } int dfs(int u,int y) { if(u==T) return y; int rest=0; for(int i=head[u];i&&rest<y;i=e[i].next) { int v=e[i].v; if(dis[v]==dis[u]+1&&e[i].c) { int x=dfs(v,min(y-rest,e[i].c)); e[i].c-=x; e[i^1].c+=x; rest+=x; } } if(!rest) dis[u]=-1; return rest; } void slove() { tot=0; for(int i=n+1;i<=n+k;i++) { tot=0;printf("%d:",i-n); for(int j=head[i];j;j=e[j].next) if(e[j^1].c&&e[j].v!=T) tmp[++tot]=e[j].v; sort(tmp+1,tmp+tot+1); for(int j=1;j<=tot;j++) printf(" %d",tmp[j]); printf("\n"); } return ; } void dinic() { while(bfs()) ans+=dfs(S,INF); if(ans==sum) slove(); else printf("NoSolution!"); } int main() { freopen("testlib.in","r",stdin); freopen("testlib.out","w",stdout); int x,t; k=read(),n=read();S=0,T=n+k+1; for(int i=1;i<=k;i++) x=read(),sum+=x,add(i+n,T,x); for(int i=1;i<=n;i++) { add(S,i,1);t=read(); while(t--) x=read(),add(i,x+n,1); } dinic(); return 0; }