【网络流24题】试题库问题-白红宇

【网络流24题】试题库问题

阅读量：5157 次

发布时间：2019-06-13

本文共 2548 字，大约阅读时间需要 8 分钟。

假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。编程任务：对于给定的组卷要求，计算满足要求的组卷方案。

由文件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.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,需要的数量)(每道题,所属类型,1)

1 #include
          
            2 #include
           
             3 #include
            
              4 #include
             
               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

转载于:https://www.cnblogs.com/Yuzao/p/6872881.html

你可能感兴趣的文章

Description

Input

Output