Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1033
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
unordered_map < int,unordered_map<int,int>> graph;
vector<int> parents;
int k,p,x,v,f;
void augment(int cur,int minEdge){
if(cur == 0){
f = minEdge;
return;
} else if(parents[cur] != -1){
int par = parents[cur];
augment(par,min(minEdge,graph[par][cur]));
graph[par][cur] -= f;
graph[cur][par] += f;
}
}
int main() {
while(scanf("%d %d",&k,&p),(k+p)!=0){
graph.clear();
// 0 - source
// 1 - sink
// 2-(k+2) - categories
// > k+2 - problems
int problemsNeeded = 0;
for(int i=0;i<k;i++){
scanf("%d",&v);
graph[0][2+i] = v;
problemsNeeded += v;
}
for(int i=0;i < p;i++){
scanf("%d",&x);
while(x--){
scanf("%d",&v);
v--;
graph[2+v][2+k+i] = 1; // category to problem
}
graph[2+k+i][1] = 1; // problem to sink
}
// edmonds karp
int mf=0;
while(1>{
f = 0;
vector < bool> visited(2+k+p);
queue<int> bfs;
parents.assign(2+k+p,-1);
bfs.push(0);
visited[0] = true;
while(!bfs.empty()){
int cur = bfs.front(); bfs.pop();
if(cur == 1) break;
for(auto& neigh : graph[cur]){
if(neigh.second>0 && !visited[neigh.first]){
parents[neigh.first] = cur;
visited[neigh.first] = true;
bfs.push(neigh.first);
}
}
}
augment(1,1e7);
if(f==0) break;
mf += f;
}
if(mf != problemsNeeded) printf("0\n");
else {
printf("1\n");
for(int i=0;i<k;i++){
bool first = true;
for(auto& neigh : graph[2+i]>{
// check backedge
if(graph[neigh.first][2+i]>0){
if(!first) printf(" ");
first = false;
printf("%d",neigh.first-k-1);
}
}
printf("\n");
}
}
}
}.Input
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
Output
8 11 12
1 6 7
2 3 4 5
0
Demonstration
UVA Online Judge solution - 10092 - The Problem with the Problem Setter - UVA Online Judge solution in C,C++,Java