Problem H
The Problem
with the Problem Setter
Input: Standard Input
Output: Standard Output
The number of students interested
to participate in this year's Intra-BUET
Programming Contest is huge. Since it is very difficult to accommodate such
a large number of students in our labs, we have decided to arrange a Screening Test. The test will be
paper-based and may include as many as 100 analytical problems from as many as
20 categories. I have been assigned the job of setting problems for this test.
At first, the job seemed to be
very easy since I was told that I would be provided with a pool of about 1000
analytical problems already divided into appropriate categories. But after
getting the problems I discovered that for many problems the original authors were
not sure about the appropriate categories and so they wrote down multiple
category-names in the category fields. Since in the Screening Test a problem cannot be placed under more than one
category and the number of problems to be set under each category is fixed,
setting problems for this test is not actually easy.
I know that a
program can be written that can do the job automatically. But since I don't
like writing programs, I seek your help.
Input
The input file may contain
multiple test cases. Each test case begins with a line containing two integers:
nk and np (2 <= nk <= 20, nk <= np <= 1000) where nk
is the number of categories and np
is the number of problems in the pool. The second line contains nk positive integers where
the i-th integer specifies the number
of problems to be included in category i
(1 <= i <= nk) of the test. You may assume that the sum of these nk integers will never exceed
100. The j-th (1 <= j <= np) of the next np
lines contains the category information of the j-th problem in the pool. A category specification for a problem
start with a positive integer not greater than nk, specifying the number of categories in one of which
this problem can be included, followed by the category numbers. Category
numbers are positive integers not greater than nk.
A test case containing two zeros
for nk and np terminates the input.
Output
For each test case in the input
print a line containing either 1 or 0 depending on whether or not problems can
be successfully selected form the pool under the given restrictions (1 for
success and 0 for failure). In case of successful selection print nk additional lines where the
i-th (1 <= i <= nk) of
these lines contains the problem numbers that can be included in category i. Problem numbers are positive integers
not greater then np and two
problem numbers must be separated by a single space character. Note that, in
case of successful selection any valid selection will be accepted.
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
3 15
7 3 4
2 1 2
1 1
1 2
1 2
1 3
3 1 2 3
2 2 3
2 2 3
1 2
1 2
2 2 3
2 2 3
2 1 2
1 1
3 1 2 3
0 0
Sample Output
1
8 11 12
1 6 7
2 3 4 5
0
__________________________________________________________________________________________
Rezaul Alam Chowdhury
"However, if we do discover a complete theory, it should in time be
understandable in broad principle by everyone, not just a few scientists. Then
we shall all, philosophers, scientists, and just ordinary people, will be able
to take part in the discussion of the question of why it is that we and the universe
exists. If we find the answer to that, it would be ultimate triumph of human
reason – for then we would know… "
題目描述:
有 nk 種領域的題目要出,而題庫中有 np 個題目,
每個領域又有各自的要出的題目數量,
在 np 個題目中,每個題目都有各自涉及的領域,
出題的時候考慮一道題目的領域滿足就好,同一道題目不以其他領域出現。
source - categories - problem - sink
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int x, y, v;// x->y, v
int next;
} edge[500005];
int e, head[1100], dis[1100], prev[1100], record[1100];
void addEdge(int x, int y, int v) {
edge[e].x = x, edge[e].y = y, edge[e].v = v;
edge[e].next = head[x], head[x] = e++;
edge[e].x = y, edge[e].y = x, edge[e].v = 0;
edge[e].next = head[y], head[y] = e++;
}
int maxflow(int s, int t) {
int flow = 0;
int i, j, x, y;
while(1) {
memset(dis, 0, sizeof(dis));
dis[s] = 0xffff; // oo
queue<int> Q;
Q.push(s);
while(!Q.empty()) {
x = Q.front();
Q.pop();
for(i = head[x]; i != -1; i = edge[i].next) {
y = edge[i].y;
if(dis[y] == 0 && edge[i].v > 0) {
prev[y] = x, record[y] = i;
dis[y] = min(dis[x], edge[i].v);
Q.push(y);
}
}
if(dis[t]) break;
}
if(dis[t] == 0) break;
flow += dis[t];
for(x = t; x != s; x = prev[x]) {
int ri = record[x];
edge[ri].v -= dis[t];
edge[ri^1].v += dis[t];
}
}
return flow;
}
int main() {
int n, m, x, y;
int i, j, k;
while(scanf("%d %d", &n, &m) == 2) {
if(n == 0) break;
e = 0;
memset(head, -1, sizeof(head));
int st = 0, ed = n+m+1;
int Pro = 0;
for(i = 1; i <= n; i++) {
scanf("%d", &x);
addEdge(m+i, ed, x);
Pro += x;
}
for(i = 1; i <= m; i++) {
scanf("%d", &x);
while(x--) {
scanf("%d", &y);
addEdge(i, m+y, 1);
}
addEdge(st, i, 1);
}
int flow = maxflow(st, ed);
if(flow == Pro) {
puts("1");
vector<int> res[n];
for(i = 1; i <= m; i++) {
for(j = head[i]; j != -1; j = edge[j].next) {
if(edge[j].v == 0 && edge[j].y > m) {
res[edge[j].y-m-1].push_back(i);
break;
}
}
}
for(i = 0; i < n; i++) {
for(j = 0; j < res[i].size(); j++) {
if(j) putchar(' ');
printf("%d", res[i][j]);
}
puts("");
}
} else
puts("0");
}
return 0;
}