Google code jam 2008, Round 1A: B.Milkshakes 贪心算法实现

原题：

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:All of these numbers are separated by single spaces.

• 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).

• An integer T >= 1, the number of milkshake types the customer likes, followed by

• 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:

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:

• The string "IMPOSSIBLE", if the customers' preferences cannot be satisfied; OR

• 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.

Limits

Small dataset

C = 100 
1 <= N <= 10 
1 <= M <= 100

Large dataset

C = 5 
1 <= N <= 2000 
1 <= M <= 2000

The sum of all the T values for the customers in a test case will not exceed 3000.

Sample

Input	Output
2 5 3 1 1 1 2 1 0 2 0 1 5 0 1 2 1 1 0 1 1 1	Case #1: 1 0 0 0 0 Case #2: IMPOSSIBLE

In the first case, you must make flavor #1 malted, to satisfy the first customer. Every other flavor can be unmalted. The second customer is satisfied by getting flavor #2 unmalted, and the third customer is satisfied by getting flavor #5 unmalted.

In the second case, there is only one flavor. One of your customers wants it malted and one wants it unmalted. You cannot satisfy them both.

一份中文翻译：

地址：here
本文仅作学习之用，题目的测试用例下载及答案的上传请到上面的英文地址，有不专业或者错误还请指正。

奶昔店

问题
你经营一家奶昔店，可以准备N种不同的口味，每一种口味又可以分成添加麦乳精（malted）和不添加麦乳精（unmalted）两种。因此，你一共可以做2N中不同口味的奶昔。
每一位顾客都有一些自己喜欢的奶昔，并且只要你能提供一种他们喜欢的口味就可以满足他们的要求。每位顾客喜欢的口味里面最多有一种是添加麦乳精的。
你要制作N桶奶昔，因此：

• 每一种口味的奶昔都会有且只有一桶，而且它要么是添加麦乳精的要么是不添加的

• 对每一位顾客，你都应该至少准备一桶他们喜欢的类型。

• 含麦乳精的桶数尽可能的最少。

 找出有没有可能在这些约束条件下满足所有的顾客，如果满足，你需要制作那些口味的奶昔。

 如果可以满足所有的顾客，那么将会只有一个答案的添加麦乳精的奶昔桶数是最少的。

 输入

•  包含一个整数C的一行，表示在输入文件里的测试用例数

 对于每一个测试用例，会有：

• 包含一个整数N的一行，奶昔口味数

• 包含一个整数M的一行，顾客数

• M行，每一行对应一个顾客，包含：

• 对于每一位顾客没有一个整数对会出现1次以上

• 每一位顾客至少有一种喜欢的口味（T >= 1)

• 每一位顾客最多喜欢一种添加麦乳精的奶昔口味。（也就是说对于每一位顾客最多有一个整数对的Y = 1）

• 一个整数T >= 1，顾客喜欢的奶昔口味数，紧接着是：

• T个整数对"X Y"，一个是表示顾客喜欢的口味，X取值从1到N（包含），另一个Y为0表示不添加麦乳精，为1表示添加麦乳精。注意：

      所有的这些数字都用空格分开。

 输出

•  C行，一行对应输入文件中出现的一个测试用例，每一行包含一个字符串"Case #X: "，X表示第几个测试用例，从1开始，紧跟着是：

• 字符串"IMPOSSIBLE"，表示如果用户的需求不能被满足 或者

• N个用空格分开的整数，表示从1到N的每一种口味，如果是0表示对应的口味应该不添加麦乳精，如果是1表示应该添加麦乳精。

限制

小数据集和

C = 100

1 <= N <= 10
1 <= M <= 100

大数据集和

 C = 5
1 <= N <= 2000
1 <= M <= 2000

 在一个测试用例中所有顾客的全部T值的和不会超过3000

例子

 输入
2
5
3
1 1 1
2 1 0 2 0
1 5 0
1
2
1 1 0
1 1 1

 输出
Case #1: 1 0 0 0 0
Case #2: IMPOSSIBLE

在第一个例子中，你必须把#1口味添加美乳精来满足第一位顾客。其他的所有口味必须是不添加麦乳精的。把#2口味不添加麦乳精满足第二位顾客的需求，把#5口味做成不添加麦乳精满足第五位顾客的需求。
在第二个例子中只有一种口味。一个顾客希望是添加麦乳精的但另一位不希望，所以你不能同时满足他们两个。

解决思路：

Using the following steps, we can quickly find whether a solution exists, and if so, what the solution is.

1. Start with every flavor unmalted and consider the customers one by one.

2. If there is an unsatisfied customer who only likes unmalted flavors, and all those flavors have been made malted, then no solution is possible.

3. If there is an unsatisfied customer who has one favorite malted flavor, then we must make that flavor malted. We do this, then go back to step 2.

4. If there are no unsatisfied customers, then we already have a valid solution and can leave the remaining flavors unmalted.

我的代码：

#include <iostream>
#include <map>
#include <vector>
using namespace std;
///////////////////////////SubMain//////////////////////////////////
class CCustomer
{
public:
	int types;
	map<int, int> malt;
	bool satisfied;
	bool isLike(int flavor, int malted)
	{
		map<int,int>::iterator it = malt.find(flavor);
		if (it != malt.end())
		{
			if (it->second == malted)
			{
				return true;
			}
			else
			{
				return false;
			}
		}
		
		return false;
	}

	bool isSatisfied(const vector<int>& flavors)
	{
		for (int i = 0; i < flavors.size(); i++)
		{
			if (isLike(i + 1, flavors[i]))
			{
				return true;
			}
		}
		return false;
	}

	int countMalted()
	{
		int m = 0;
		for (map<int, int>::iterator it = malt.begin(); it != malt.end(); it++)
		{
			if (it->second == 1)
			{
				m++;
			}
		}

		return m;
	}
};
int main(int argc, char *argv[])
{
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	int nCases = 0;
	cin >> nCases;
	cin.get();
	for (int i = 0; i < nCases; i++)
	{
		cout << "Case #" << i + 1 << ": ";
		int flavors = 0;
		cin >> flavors;
		vector<int> milkshakes;
		vector<CCustomer> allCustomers;
		int customers = 0;
		cin >> customers;
		for (int j = 0; j < customers; j++)
		{
			CCustomer c;
			cin >> c.types;
			for (int k = 0; k < c.types; k++)
			{
				int x = 0;
				int y = 0; 
				cin >> x;
				cin >> y;
				c.malt[x] = y;
				c.satisfied = false;
			}
			allCustomers.push_back(c);
		}

		for (int j = 0; j < flavors; j++)
		{
			int n = 0;
			milkshakes.push_back(n);
		}

		for (int j = 0; j < customers; j++)
		{
			CCustomer c = allCustomers[j];
			if (!c.isSatisfied(milkshakes))
			{
				if (c.countMalted() == 0)
				{
					// 客户只喜欢unmalted
					bool all_malted = true;
					for (map<int, int>::iterator it = c.malt.begin(); it != c.malt.end(); it++)
					{
						if (milkshakes[it->first - 1] != 1)
						{
							all_malted = false;
							break;
						}
					}
					if (all_malted)
					{
						customers = -1;				 // 用-1表示这个case无解
						break;
					}
				}

				if (customers >= 0)
				{
					for (map<int, int>::iterator it = c.malt.begin(); it != c.malt.end(); it++)
					{
						if (it->second == 1)
						{
							milkshakes[it->first - 1] = 1;
							j = -1;
							break;
						}
					}
				}
			}
		}
		
		
		if (customers < 0)
		{
			cout << "IMPOSSIBLE" << endl;
		}
		else
		{
			for (int j = 0; j < flavors; j++)
			{
				cout << milkshakes[j] << " ";
			}
			cout << endl;
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » Google code jam 2008, Round 1A: B.Milkshakes 贪心算法实现