2193.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2193 on 2006-04-03 at 22:32:20 */ 
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

const int N = 12;
const int S_MAX = 1 << N;
const int INF = 1 << 30;
const char SEM[] = "FS";

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

map<const char*, int, cmp> dict;
int n, m, sem[2][S_MAX]; // F && S

class Course {
public:
	char name[8], tp;
	vector<int> prev;
	void make();
	bool canGo(int) const;
	bool canChose(char) const;
};
void Course::make() {
	prev.clear();
	int i, pn; scanf("\n%c %d", &tp, &pn);
	for(i = 0; i < pn; i++) {
		char nm[8]; scanf("%s", nm);
		prev.push_back(dict.find(nm)->second);
	}
}
bool Course::canGo(int status) const {
	int i;
	for(i = 0; i < (int)prev.size(); i++)
		if(!(status&(1<<prev[i]))) return false;
	return true;
}
bool Course::canChose(char t) const {
	if(tp == 'B') return true;
	else return (t == tp);
}

Course crs[N];
int may[N], myn, eq[N];

bool legal(int);
void update(int, int);
void enumer(int, int, int, int);

int main()
{
	int i, j;

	while(scanf("%d %d", &n, &m) != EOF && n > 0) {
		int status = 1 << n; dict.clear();
		for(i = 0; i < 2*status; i++) sem[i&1][i>>1] = INF;
		sem[0][0] = 0;
		for(i = 0; i < n; i++) { scanf("%s", crs[i].name); dict[crs[i].name] = i; }
		for(i = 0; i < n; i++) {
			char name[8]; scanf("%s", name);
			int o = dict.find(name)->second;
			crs[o].make();
		}
		for(i = 0; i < status; i++) {
			sem[0][i] = min(sem[0][i], sem[1][i]+1); sem[1][i] = min(sem[1][i], sem[0][i]+1);
			for(j = 0; j < 2; j++)
				if(legal(i)) update(i, j);
		}
		printf("The minimum number of semesters required to graduate is %d.\n", 
			min(sem[0][status-1], sem[1][status-1]));
	}
	
	return 0;
}

bool legal(int status)
{
	int i;
	for(i = 0; i < n; i++)
		if((status&(1<<i)) && !crs[i].canGo(status)) return false;
	return true;
}
void update(int st, int se)
{
	int i;
	for(myn = i = 0; i < n; i++)
		if(!(st&(1<<i)) && crs[i].canGo(st) && crs[i].canChose(SEM[se])) may[myn++] = i;
	enumer(st, se, 0, 0);
}
void enumer(int st, int se, int o, int b)
{
	int i;
	if(o == m || b == myn) {
		int ps = st;
		for(i = 0; i < o; i++) st |= 1 << eq[i];
		sem[1-se][st] = min(sem[1-se][st], sem[se][ps]+1);
	} else {
		for(i = b; i < myn; i++) {
			eq[o] = may[i];
			enumer(st, se, o+1, i+1);
		}
	}
}