2055.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2055 on 2006-01-07 at 12:44:46 */ 
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;

const int MAX = 16;
const int L_MAX = 32;

struct cmp {
	bool operator ()(const char* s1, const char* s2) const {
		return strcmp(s1, s2) < 0;
	}
};

bool used[MAX];
int cn, clr[MAX];

int color(bool[MAX][MAX], int, int, int);

int main()
{
	map<const char*, int, cmp> male, female;
	char name[2][MAX][L_MAX], chara[L_MAX];
	int m, f, s, n;
	int i, j, k, t;
	bool act[2][MAX][MAX];
	
	for(t = 1; scanf("%d %d %d", &m, &f, &s) != EOF && m*f*s != 0; t++) {
		male.clear(); female.clear();
		for(i = 0; i < m; i++) {
			scanf("%s", name[0][i]);
			male[name[0][i]] = i;
		}
		for(i = 0; i < f; i++) {
			scanf("%s", name[1][i]);
			female[name[1][i]] = i;
		}
		memset(act, false, sizeof(act));
		for(i = 0; i < s; i++) {
			int ml[MAX], mn = 0;
			int fl[MAX], fn = 0;
			scanf("%d", &n);
			for(j = 0; j < n; j++) {
				scanf("%s", chara);
				if(male.count(chara) != 0) ml[mn++] = male.find(chara)->second;
				else fl[fn++] = female.find(chara)->second;
			}
			for(j = 0; j < mn; j++) {
				for(k = j+1; k < mn; k++) {
					act[0][ml[j]][ml[k]] = act[0][ml[k]][ml[j]] = true;
				}
			}
			for(j = 0; j < fn; j++) {
				for(k = j+1; k < fn; k++) {
					act[1][fl[j]][fl[k]] = act[1][fl[k]][fl[j]] = true;
				}
			}
		}
		printf("Movie #%d\n", t);
		int ma = color(act[0], 0, m, 0), fa = color(act[1], 0, f, 0);
		printf("You need %d actor%s and %d actress%s.\n\n", 
			ma, (ma == 1 ? "" : "s"), fa, (fa == 1 ? "" : "es"));
	}
	
	return 0;
}

int color(bool act[MAX][MAX], int b, int n, int total)
{
	if(b == 0) {
		cn = MAX; memset(clr, -1, sizeof(clr));
		memset(used, false, sizeof(used));
	}
	if(b == n) cn = min(cn, total);
	else {
		int i, j;
		for(i = 0; i <= total; i++) {
			bool can = true;
			for(j = 0; j < n && i != total; j++) {
				if(act[b][j] && clr[j] == i) { can = false; break; }
			}
			int cln = (i == total) ? total+1 : total;
			if(can && cln < cn) {
				clr[b] = i;
				color(act, b+1, n, cln);
				clr[b] = -1;
			}
		}
	}
	
	return cn;
}