Description?

假設(shè)一個試題庫中有n道試題。每道試題都標(biāo)明了所屬類別。同一道題可能有多個類別 屬性。現(xiàn)要從題庫中抽取m 道題組成試卷。并要求試卷包含指定類型的試題。試設(shè)計(jì)一個 滿足要求的組卷算法。 編程任務(wù)： 對于給定的組卷要求，計(jì)算滿足要求的組卷方案。

Input?

由文件input.txt提供輸入數(shù)據(jù)。文件第1行有2個正整數(shù)k和n (2 <=k<= 20, k<=n<= 1000) k 表示題庫中試題類型總數(shù)，n 表示題庫中試題總數(shù)。第2 行有k 個正整數(shù)，第i 個正整數(shù) 表示要選出的類型i 的題數(shù)。這k個數(shù)相加就是要選出的總題數(shù)m。接下來的n行給出了題 庫中每個試題的類型信息。每行的第1 個正整數(shù)p表明該題可以屬于p類，接著的p個數(shù)是 該題所屬的類型號。

Output?

程序運(yùn)行結(jié)束時，將組卷方案輸出到文件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 3 Sample Output 1: 1 6 8 2: 7 9 10 3: 2 3 4 5 題解： (S,每一道題,1) (每種題型,T,需要的數(shù)量)(每道題,所屬類型,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(){ 8 int str=0;char ch=getchar(); 9 while(ch>'9'||ch<'0')ch=getchar(); 10 while(ch>='0' && ch<='9')str=str*10+ch-'0',ch=getchar(); 11 return str; 12 } 13 int n,m,S=0,T,num=1,head[N]; 14 struct Lin{ 15 int next,to,dis; 16 }a[N*N]; 17 void init(int x,int y,int z){ 18 a[++num].next=head[x]; 19 a[num].to=y; 20 a[num].dis=z; 21 head[x]=num; 22 a[++num].next=head[y]; 23 a[num].to=x; 24 a[num].dis=0; 25 head[y]=num; 26 } 27 int dep[N],q[N]; 28 bool bfs() 29 { 30 memset(dep,0,sizeof(dep)); 31 dep[S]=1;q[1]=S;int u,t=0,sum=1,x; 32 while(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 } 41 return dep[T]; 42 } 43 int dfs(int x,int flow) 44 { 45 if(x==T || !flow)return flow; 46 int u,tmp,sum=0; 47 for(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 } 55 return sum; 56 } 57 int main() 58 { 59 int x,k,sum1=0; 60 m=gi();n=gi(); 61 T=n+m+1; 62 for(int i=1;i<=m;i++){ 63 x=gi();init(i+n,T,x);sum1+=x; 64 } 65 for(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 } 70 int tot=0,tmp; 71 while(bfs()){ 72 tmp=dfs(S,INF); 73 while(tmp)tot+=tmp,tmp=dfs(S,INF); 74 } 75 if(tot<sum1){ 76 puts("No Solution!"); 77 return 0; 78 } 79 for(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 } 85 return 0; 86 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Yuzao/p/6872881.html

總結(jié)

以上是生活随笔為你收集整理的【网络流24题】试题库问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。