Description
假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别 属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个 满足要求的组卷算法。 编程任务： 对于给定的组卷要求，计算满足要求的组卷方案。Input
由文件input.txt提供输入数据。文件第1行有2个正整数k和n (2 <=k<= 20, k<=n<= 1000) k 表示题库中试题类型总数，n 表示题库中试题总数。第2 行有k 个正整数，第i 个正整数 表示要选出的类型i 的题数。这k个数相加就是要选出的总题数m。接下来的n行给出了题 库中每个试题的类型信息。每行的第1 个正整数p表明该题可以属于p类，接着的p个数是 该题所属的类型号。Output
程序运行结束时，将组卷方案输出到文件output.txt 中。文件第i 行输出 “i：”后接类 型i的题号。如果有多个满足要求的方案，只要输出1 个方案。如果问题无解，则输出“No Solution!”。Sample Input
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 3Sample Output1: 1 6 8 2: 7 9 10 3: 2 3 4 5题解：(S,每一道题,1) (每种题型,T,需要的数量)(每道题,所属类型,1)
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=1205,INF=1999999999; 7 int gi(){ 8int str=0;char ch=getchar(); 9while(ch>'9'||ch<'0')ch=getchar();10while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar();11return str;12 }13 int n,m,S=0,T,num=1,head[N];14 struct Lin{15int next,to,dis;16 }a[N*N];17 void init(int x,int y,int z){18a[++num].next=head[x];19a[num].to=y;20a[num].dis=z;21head[x]=num;22a[++num].next=head[y];23a[num].to=x;24a[num].dis=0;25head[y]=num;26 }27 int dep[N],q[N];28 bool bfs()29 {30memset(dep,0,sizeof(dep));31dep[S]=1;q[1]=S;int u,t=0,sum=1,x;32while(t!=sum)33{34 x=q[++t];35 for(int i=head[x];i;i=a[i].next){36 u=a[i].to;37 if(dep[u] || a[i].dis<=0)continue;38 dep[u]=dep[x]+1;q[++sum]=u;39 }40}41return dep[T];42 }43 int dfs(int x,int flow)44 {45if(x==T || !flow)return flow;46int u,tmp,sum=0;47for(int i=head[x];i;i=a[i].next){48 u=a[i].to;49 if(dep[u]!=dep[x]+1 || a[i].dis<=0)continue;50 tmp=dfs(u,min(flow,a[i].dis));51 a[i].dis-=tmp;a[i^1].dis+=tmp;52 sum+=tmp;flow-=tmp;53 if(!flow)break;54}55return sum;56 }57 int main()58 {59int x,k,sum1=0;60m=gi();n=gi();61T=n+m+1;62for(int i=1;i<=m;i++){63 x=gi();init(i+n,T,x);sum1+=x;64}65for(int i=1;i<=n;i++){66 init(S,i,1);67 k=gi();68 for(int j=1;j<=k;j++)x=gi(),init(i,x+n,1);69}70int tot=0,tmp;71while(bfs()){72 tmp=dfs(S,INF);73 while(tmp)tot+=tmp,tmp=dfs(S,INF);74}75if(tot<sum1){76 puts("No Solution!");77 return 0;78}79for(int i=1+n;i<=n+m;i++){80 printf("%d:",i-n);81 for(int j=head[i];j;j=a[j].next)82 if(a[j].to!=T && a[j].dis==1)printf(" %d",a[j].to);83 puts("");84}85return 0;86 }
如果觉得《【网络流24题】试题库问题》对你有帮助，请点赞、收藏，并留下你的观点哦！
