经过吴垠点化才想明白这个题该如何做。
先说一下这个题目的条件：
Problem
You own a milkshake shop. There are N different flavors that you can prepare, and each flavor can be prepared "malted" or "unmalted". So, you can make 2N different types of milkshakes.
Each of your customers has a set of milkshake types that they like, and they will be satisfied if you have at least one of those types prepared. At most one of the types a customer likes will be a "malted" flavor.
You want to make N batches of milkshakes, so that:
* There is exactly one batch for each flavor of milkshake, and it is either malted or unmalted.
* For each customer, you make at least one milkshake type that they like.
* The minimum possible number of batches are malted.
Find whether it is possible to satisfy all your customers given these constraints, and if it is, what milkshake types you should make.
If it is possible to satisfy all your customers, there will be only one answer which minimizes the number of malted batches.
Input
* One line containing an integer C, the number of test cases in the input file.
For each test case, there will be:
* One line containing the integer N, the number of milkshake flavors.
* One line containing the integer M, the number of customers.
* M lines, one for each customer, each containing:
o An integer T >= 1, the number of milkshake types the customer likes, followed by
o T pairs of integers "X Y", one for each type the customer likes, where X is the milkshake flavor between 1 and N inclusive, and Y is either 0 to indicate unmalted, or 1 to indicated malted. Note that:
+ No pair will occur more than once for a single customer.
+ Each customer will have at least one flavor that they like (T >= 1).
+ Each customer will like at most one malted flavor. (At most one pair for each customer has Y = 1).
All of these numbers are separated by single spaces.
Output
* C lines, one for each test case in the order they occur in the input file, each containing the string "Case #X: " where X is the number of the test case, starting from 1, followed by:
o The string "IMPOSSIBLE", if the customers' preferences cannot be satisfied; OR
o N space-separated integers, one for each flavor from 1 to N, which are 0 if the corresponding flavor should be prepared unmalted, and 1 if it should be malted.
这里面需要注意的条件是，每个顾客的malted需求只有1,正是这个条件使得题目的解法变的简单快捷了。
可以这样考虑这个题目，在最好的情况下，所有flavor都是unmalted的，当然，可能会出现不满足这种情况的状态，因为每个顾客至多有一个malted需求,所以只有当某个顾客只有一个需求且该需求为malted时，才需要把该flavor设置为malted，这里的只有一个需求是在下面这种情况下的：
当某个flavor被设置为malted后，所有要求该flavor为unmalted的需求都应该在顾客的需求列表中删除，这样每个顾客选择flavor的范围就会缩小，当顾客只有一个为malted需求，则需要把该flavor也设置为malted。
如果有顾客选择flavor的范围变为0时，则输出impossible。
有个地方需要注意，就是当输入的数据中所有顾客选择flavor的范围都大于1个时，则输出肯定为全0。
我的代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct tt
{
int n;
int flag;
};
struct tt abc[2010][3010];
int flavor[2500][2010][2];
int flavor1[2500];
int one_queue[2500][2];
int queue_flag[2500];
int one_start, one_end;
int n, m;
int enqueue(int a[2])
{
one_queue[one_end][0] = a[0];
one_queue[one_end][1] = a[1];
one_end++;
return 0;
}
int dequeue(int a[2])
{
if (one_end == one_start) {
return -1;
}
//one_end--;
a[0] = one_queue[one_start][0];
a[1] = one_queue[one_start][1];
one_start++;
return 0;
}
int comp1(const void *a, const void *b)
{
int t = (((struct tt *)b)->flag) - (((struct tt *)a)->flag);
return t;
}
int main(int argc, char **argv)
{
int c, i, j, k, t, ret;
int a[2], b[2];
scanf("%d", &c);
for (i = 1; i <= c; i++) {
again:
if (i > c)
break;
scanf("%d", &n);
scanf("%d", &m);
memset(flavor1, 0, sizeof flavor1);
memset(flavor, 0, sizeof flavor);
memset(abc, 0, sizeof abc);
memset(one_queue, 0, sizeof one_queue);
memset(queue_flag, 0, sizeof queue_flag);
one_start = one_end = 0;
for (j = 1; j <= m; j++) {
scanf("%d", &abc[j][0].n);
abc[j][0].flag = 1;
t = 0;
for (k = 1; k <= abc[j][0].n; k++) {
scanf("%d", &abc[j][k].n);
scanf("%d", &abc[j][k].flag);
ret = ++(flavor[abc[j][k].n][0][0]);
flavor[abc[j][k].n][ret][0] = j;
flavor[abc[j][k].n][ret][1] = abc[j][k].flag;
}
qsort(&(abc[j][1]), abc[j][0].n, sizeof(struct tt), comp1);
if (abc[j][0].n == 1 && abc[j][1].flag == 1 && (!queue_flag[abc[j][1].n])) {
a[0] = j;
a[1] = abc[j][1].n;
enqueue(a);
queue_flag[abc[j][1].n] = 1;
}
}
printf("Case #%d:", i);
if (one_end - one_start == 0) {
for (j = 1; j <= n; j++) {
printf(" 0");
}
printf("\n");
continue;
}
while (dequeue(a) != -1) {
if (flavor1[a[1]] == 1)
continue;
flavor1[a[1]] = 1;
for (j = 1; j <= flavor[a[1]][0][0]; j++) {
if (flavor[a[1]][j][1] != 1) {
abc[flavor[a[1]][j][0]][0].n--;
if (abc[flavor[a[1]][j][0]][0].n <= 0) {
printf(" IMPOSSIBLE\n");
i++;
goto again;
}
else if (abc[flavor[a[1]][j][0]][0].n == 1 && abc[flavor[a[1]][j][0]][1].flag == 1) {
if (!queue_flag[abc[flavor[a[1]][j][0]][1].n]) {
b[0] = flavor[a[1]][j][0];
b[1] = abc[flavor[a[1]][j][0]][1].n;
enqueue(b);
}
}
}
}
}
for (j = 1; j <= n; j++) {
printf(" %d", flavor1[j]);
}
printf("\n");
}
return 0;
}
|
阅读(2129) | 评论(1) | 转发(0) |
