传送门 ↬ \looparrowright ↬
题目描述
问题描述
假设一个试题库中有 n n n 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 m m m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。
编程任务
对于给定的组卷要求,计算满足要求的组卷方案。
输入格式
第一行有两个正整数 k k k 和 n n n 。k k k 表示题库中试题类型总数,n n n 表示题库中试题总数。
第二行有 k k k 个正整数,第 i i i 个正整数表示要选出的类型 i i i 的题数。这 k k k 个数相加就是要选出的总题数 m m m 。
接下来的 n n n 行给出了题库中每个试题的类型信息。每行的第一个正整数 p p p 表明该题可以属于 p p p 类,接着的 p p p 个数是该题所属的类型号。
输出格式
输出共 k k k 行,第 i i i 行输出 i:
后接类型 i i i 的题号。
如果有多个满足要求的方案,只要输出一个方案。
如果问题无解,则输出No Solution!
。
输入输出样例
输入 #1
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
输出 #1
1: 1 6 8
2: 7 9 10
3: 2 3 4 5
说明/提示
2 ⩽ k ⩽ 20 2\leqslant k \leqslant 20 2 ⩽ k ⩽ 20 ,k ⩽ n ⩽ 1 0 3 k \leqslant n \leqslant 10^3 k ⩽ n ⩽ 1 0 3 。
分析
首先要明确一下题意,题目描述有一些不严谨。事实上,每道题虽可以属于多个类型,但却只能与一种类型相匹配,即最后输出时不能在不同种类型中出现同一道题。
每个类型之间和每道题目直接都不会有内在联系,此题要求进行类型与题目的匹配:要求一个类型有多个题目,可以建立二分图多重匹配模型。首先规定节点编号,编号为 1 ∼ n 1\sim n 1 ∼ n 的节点表示题目,编号为 n + 1 ∼ n + k n+1\sim n+k n + 1 ∼ n + k 的节点表示类型。若题目 i i i 属于类型 j j j ,则建立一条 i i i 到 j + n j+n j + n 的边。
网络流是解决二分图最常用也是较为高效的方法。设超级源点 s s s ,编号为 0 0 0 ;超级汇点 t t t ,编号为 n + k + 1 n+k+1 n + k + 1 。接下来考虑如何设置各条边的容量,其核心是:通过设置容量来保证网络流量具有实际意义 。令 s s s 向 1 ∼ n 1\sim n 1 ∼ n 的节点连边,容量为 1 1 1 ,题目节点和类型节点之间的边容量也设置为 1 1 1 ,这就意味着一道题目至多只会被使用一次。接着令 n + 1 ∼ n + k n+1\sim n+k n + 1 ∼ n + k 的节点向 t t t 连边,容量为各个类型需要的题目数量;这就意味着网络最大流一定不超过 m m m ,并且,当最大流达到 m m m 时,流入 n + 1 ∼ n + k n+1\sim n+k n + 1 ∼ n + k 中任意节点的流量就等于该点表示的类型需要的题目数量。
建图完成后,用 Dinic \text{Dinic} Dinic 算法计算出最大流 m a x f l o w \mathrm{maxflow} maxflow ,若 maxflow = m \text{maxflow}=m maxflow = m ,则存在匹配方案;否则,不存在。当存在匹配方案时,需要考虑匹配方案如何输出。我们注意到,Dinic \text{Dinic} Dinic 算法建边时,会相应建立一条反向边,在残量网络上增广时,反向边的容量会被改变;反向边容量初始为 0 0 0 ,若反向边容量不为零,说明其对应的正向边对最大流有贡献。因此,不妨枚举由类型节点流向题目节点的反向边,若反向边指向一个题目节点,且其上的流量不为零,说明该题目与该类型匹配。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 #include <cstring> #include <iostream> #include <queue> #include <cstdio> using namespace std;const int N=1006 ;const int inf=0x3f3f3f3f ;struct E { int to; int cap; int Next; }edge[N*N<<1 ]; int head[N],tot;int s,t;int depth[N];int n,k,m;void init () ;inline void add_edge (int ,int ,int ) ;bool bfs () ;int dfs (int x,int flow) ;int Dinic () ;int main () { cin>>k>>n; init (); int i,j; for (i=1 ;i<=k;i++) { int num; scanf ("%d" ,&num); m+=num; add_edge (n+i,t,num); } for (i=1 ;i<=n;i++) { int p; scanf ("%d" ,&p); while (p--) { int type; scanf ("%d" ,&type); add_edge (i,type+n,1 ); } } for (i=1 ;i<=n;i++) add_edge (s,i,1 ); if (Dinic ()==m) { for (i=1 ;i<=k;i++) { printf ("%d: " ,i); for (j=head[i+n];~j;j=edge[j].Next) { if (edge[j].to>n||edge[j].to==s) continue ; if (edge[j].cap) printf ("%d " ,edge[j].to); } putchar ('\n' ); } } else puts ("No Solution!" ); return 0 ; } void init () { tot=1 ; s=0 ; t=n+k+1 ; memset (head,-1 ,sizeof (head)); } inline void add_edge (int u,int v,int cap) { tot++; edge[tot].to=v; edge[tot].cap=cap; edge[tot].Next=head[u]; head[u]=tot; tot++; edge[tot].to=u; edge[tot].cap=0 ; edge[tot].Next=head[v]; head[v]=tot; } bool bfs () { memset (depth,0 ,sizeof (depth)); queue<int >q; q.push (s); depth[s]=1 ; while (!q.empty ()) { int x=q.front (); q.pop (); for (register int i=head[x];~i;i=edge[i].Next) { int y=edge[i].to; if (edge[i].cap&&!depth[y]) { q.push (y); depth[y]=depth[x]+1 ; if (y==t) return 1 ; } } } return 0 ; } int dfs (int x,int flow) { if (x==t) return flow; int rest=flow; int temp; for (register int i=head[x];~i&&rest;i=edge[i].Next) { int y=edge[i].to; if (edge[i].cap&&depth[y]==depth[x]+1 ) { temp=dfs (y,min (rest,edge[i].cap)); if (!temp) depth[y]=0 ; edge[i].cap-=temp; edge[i^1 ].cap+=temp; rest-=temp; } } return flow-rest; } int Dinic () { int maxflow=0 ; while (bfs ()) maxflow+=dfs (s,inf); return maxflow; }