«问题描述：
假设一个试题库中有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
和圆桌问题基本一样。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1101 10 #define llg int 11 #define inf (llg)1e16 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 13 llg n,m,r[maxn],c[maxn],N,tot,k; 14 15 struct DINIC 16 { 17 vector<llg>a[maxn],ba[maxn],val[maxn]; 18 llg dl[maxn],deep[maxn],bj[maxn]; 19 20 void insert(llg x,llg y,llg z) 21 { 22 a[x].push_back(y),val[x].push_back(z); 23 a[y].push_back(x),val[y].push_back(0); 24 ba[x].push_back(a[y].size()-1); ba[y].push_back(a[x].size()-1); 25 } 26 27 llg dfs(llg x,llg low) 28 { 29 llg va=0,inc=0; 30 if (x==N) return low; 31 llg w=a[x].size(); 32 for (llg i=0;i<w;i++) 33 if (deep[x]+1==deep[a[x][i]] && val[x][i]>0 && (va=dfs(a[x][i],min(low,val[x][i])))) 34 { 35 val[x][i]-=va; val[a[x][i]][ba[x][i]]+=va; inc+=va; 36 return va; 37 } 38 if (!inc) deep[x]=-1; 39 return 0; 40 } 41 42 void fencen() 43 { 44 llg x,w,v; deep[0]=0; 45 memset(bj,0,sizeof(bj)); 46 llg head=0,tail=1; dl[1]=0; bj[0]=1; 47 do 48 { 49 x=dl[++head]; w=a[x].size(); 50 for (llg i=0;i<w;i++) 51 { 52 v=a[x][i]; 53 if (bj[v] || val[x][i]<=0) continue; 54 dl[++tail]=v; 55 deep[v]=deep[x]+1; bj[v]=1; 56 } 57 }while (head!=tail); 58 } 59 60 llg dinic() 61 { 62 llg ans=0; 63 while (1) 64 { 65 fencen(); 66 if (!bj[N]) break; 67 ans+=dfs(0,inf); 68 } 69 return ans; 70 } 71 72 void oupt() 73 { 74 for (llg i=1;i<=k;i++) 75 { 76 printf("%d: ",i); 77 llg w=a[i].size(); 78 for (llg e=0;e<w;e++) 79 { 80 llg v=a[i][e]; 81 if (v>k && v<N && val[i][e]==0) printf("%d ",v-k); 82 } 83 printf(" "); 84 } 85 } 86 }G; 87 88 void init() 89 { 90 llg x,p; 91 cin>>k>>n; 92 for (llg i=1;i<=k;i++) 93 { 94 scanf("%d",&x); 95 G.insert(0,i,x); tot+=x; 96 } 97 for (llg j=1;j<=n;j++) 98 { 99 scanf("%d",&p); 100 for (llg i=1;i<=p;i++) 101 { 102 scanf("%d",&x); 103 G.insert(x,k+j,1); 104 } 105 G.insert(k+j,k+n+1,1); 106 } 107 N=n+k+1; 108 } 109 110 int main() 111 { 112 yyj("testlib"); 113 init(); 114 if (G.dinic()==tot) 115 { 116 // puts("1"); 117 G.oupt(); 118 } 119 else 120 { 121 puts("NoSolution!"); 122 } 123 return 0; 124 }